1、郝斌老师数据结构笔记数据结构概述 定义：我们如何把现实中大量而复杂的问题已特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上位实现某个功能二执行的相应操作，这个相应的操作也叫算法。数据结构解决存储问题，算法解决数据间的关系。数据结构=个体+个体的关系算法=对存储数据的操作。 狭义的算法算法：解题的方法和步骤 衡量算法的标准：1时间复杂度 大概程序要执行的次数，而非执行的时间：运行步骤最多的最关最核心的要运行的次数可以大概代表 2空间复杂度：算法执行过程中大概所占有的最大内存。 3 难易程度 4健壮性前两个最重要（一般算法有循环）第三个内容：数据结构的地位（数据结构是软件中最
2、核心的课程）数据库和数据结构的区别：数据库是数据结构的简化版程序：数据的存储+数据段操作+可以被计算机之行的语言预备知识：伪算法不是真正的算法通过语言来实现伪算法，希望编程语言实现要通过指针。链表的知识很重要，以后都会用到。C+的指针不够，学C语言的用途是为了以后能看懂更高级的语言*p就代表一个变量，例如i 。int*p表示定义一个存放整形变量的地址的指针变量。程序运行完，内存就终止了。 复习：1:指针：int *p/p 是个变量名字，用来存放地址，只能存储int型变量的地址指针的重要性：是C语言的灵魂， 定义 地址 内存单元的编号（cpu只能访问内存，不能访问硬盘） 从0开始的非负整数，范围
3、为04g-1 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针和指针变量不一样 指正的本质是一个操作受限的非负整数 分类： 1 基本类型的指针（p=&i表示指针变量存储i的地址，但是p为p，i为i两者无任何关系，但是*p和i却是等效的两者可以互换） 22:指针结构体3:动态内存的分配和释放。4：内存的基本单位是字节5：&为取地址符号6:# include void f(int *p) *p=100 int main() int i=9； f(&i) printf(i=%dn,i);return 0 如何实现被掉函数修改主调函数中普通变量的值1：实参为相关变量的地址（&i）2：
4、形参为以该变量的类型（int型）为类型的指针变量（指针变量p）3：在被调函数中通过 *形参变量名 的方式就可以修改主函数中普通变量的值（*p和i可以等效替换两者无任何区别）指针和数组（Array）数组名 一位数组名a是个指针常量 它存放的是一维数组第一个元素的地址， 它的值不能被改变 一维数组名指向的是数组的第一个元素。下表和指针的关系 ai*（a+i）下标和指针的关系 假设指针变量的名字为p 则p+i的值是p+i*（p所指向的变量所占的字节数）指针变量的运算 指针变量不能相加，乘除。 如果两指针变量属于同一数组，则可以相减 指针变量可以相减一整数，前提是最终结果不能草果指针的范围 p+i的值
5、是p+i*(p所指向的变量所占的字节数) p-i的值是p-i*（p所指向的变量所占的字节数） p+=p+1如何通过被调函数修改主函数中一位数组的内容 两个参数 存放数组首元素的指针变量 存放数组元素长度的整形变量# includestdio.hvoid show-array（int *p ，int len）p2=-1;/p0=*p p2=*(p+2)=*(a+2)=a2/p【i】此时就是主函数的a【i】int main (void )int a5=11,2,3,4,5;show_arraya(a,5)/a等价于&a0,&a0本身就是int *类型return 0一个double占八个字节，一个
6、字节是8位，美一个字节都占一个地址。指针变量都只占四个字节p=&x 表示p只代表x的第一个字节的地址如何通过函数修改时惨的值 #include void f（int * q）/函数声明int main (void) int i=9; int*p=&i；/ 等效为int *p; p=&i;printf (%pn,p)；/%P 表示输出指针变量所指向的元素的地址例如此例中就输出的事i的地址。 return 0;void f( int *q) *q=(int *)0xFFFFFFFF；/（int*）表示强制转换0xFFFFFFFF为地址，如果不强制转换0xFFFFFFFF只表示一个十六进制的数如果想
7、改写一个变量的值，只需要发送它的地址给被掉函数，否则无法实现对主函数中变量的值的改变。结构体：为什么会出现结构体：为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体：（是 c+中类的过度）是用户根据实际需要自己定义的复合数据类型如何使用结构体：struct Student=1000,”zhangshan”,20; 结构体 Struct sudent * pst =&st; 1; st.sid 2. pst-sid Pst所指向的结构体中的sid这个成员注意事项；结构体变量不能加减乘除，但是可以相互赋值 普通结构体变量和结构体指针变量作为函数传参的问题#include#incl
8、ude/一串，一行struct 结构体Student int sid; char name200; int age;/分号不能省int main(void) struct Student st=1000,zhangshan,20; printf(%d %s %dn,st.sid,st.name,st.age); st.sid=99; strcpy(st.name,lisi);/st.name=lisi;error st.age=22; printf(%d %s %dn,st.sid,st.name,st.age); /printf(%d %s %dn,st); return 0;结构体2#in
9、clude#include/一串，一行struct 结构体Student int sid; char name200; int age;/分号不能省int main(void)结构体 Struct Student st=1000，“张三”，20； /st.sid=99;第一种方式 Struct Student* pst；/定义一个指针变量，此指针变量只能存放我们自己定义的Struct Student类型的变量的地址 Pst=&st; Pst-sid=99;/pst-sid等价于（*pst）.sid 而（*pst）.sid等价于st.sid,所以pst-sid=st.sid return 0；第
10、八次课:结构体：1：为什么会出现结构体为了表示一些复杂的数据，而普通的基本类型变量无法满足要求2：什么叫做结构体用户根据实际需要自己定义的复合数据类型3：如何使用结构体算法1：# includestruct Student int sid; char name100; int age; ;int main () struct Student st = 2013213990,wangchuankun,20 ; printf (%d %s %dn,st.sid,st.name,st.age); return 0;输出结果：-2013213990 wangchuankun 2请按任意键继续. . .
11、有两种方式：1：4：注意事项结构提变量不能加减乘除，但是可以相互赋值。结构提变量和结构体指针变量作为函数传参算法2：算法目的：通过结构体调用指针给主函数中结构体变量赋值#include #include struct Student int sid; char name200; int age; ;void f(struct Student *pst) (*pst).sid = 2013213990; strcpy (pst-name,wangchuankun); pst-age = 22;int main () struct Student st; f(&st); printf (%d %s
12、 %dn,st.sid,st.name,st.age); return 0;运行结果：2013213990 wangchuankun 22请按任意键继续. . .算法3：算法目的：通过结构体调用指针给主函数中结构体变量赋值并且通过函数调用将主函数中的结构体变量依次输出。#include #include struct Student int sid; char name100; int age; ;void f(struct Student *pst) (*pst).sid = 2013213990; strcpy(pst-name,汪传坤); pst-age = 20;void g(stru
13、ct Student *pst) printf ( 学号：%dn 姓名：%sn 年龄：%dnn,pst-sid,pst-name,pst-age);int main() struct Student st; f (&st); g (&st); return 0;运行结果：学号：2013213990姓名：汪传坤年龄：20请按任意键继续. . . 跨函数使用内存必须要通过动态分配来完成！算法4：跨函数使用内存必须通过动态分配内存来实现# include # include int f(int*q) int i; *q = (int *)malloc(16); /*for (i = 0;i4;i+)
14、 printf (%dn,qi); */ return 0;int main () int i; int *p; f (&p); for (i = 0;i 4;i+) scanf (%d,&pi); for (i = 0;i4;i+) printf (%dn,pi); return 0; 运行结果：7845891278458912请按任意键继续. . .算法总结：通过把指针变量的地址发给形参变量q（int*q表示q是存放int*类型变量的地址q本身是一个变量， ）算法5：# include # include struct Student int sid; int age;struct Stu
15、dent *CreateStudent(void);void ShowStudent (struct Student *);int main () struct Student *ps; ps = CreateStudent(); ShowStudent(ps); return 0;void ShowStudent(struct Student *pst) printf (%d %dn,pst-sid,pst-age); struct Student * CreateStudent(void) struct Student *p = (struct Student *)malloc(sizeo
16、f(struct Student); p-sid = 99; p-age = 88; return p;运算结果：99 88请按任意键继续. . .注：只能通过动态分配内存通过调用函数分配内存才有效。数据结构正式课程模块一：算法1；静态调用函数：# include int f() int j = 20; return j;int main () int i; i = f(); printf (%dn,i); return 0; #include #include #include struct Arr/定义数据类型 ,数据类型名为struct Arr，该数据类型含有三个成员。没有定义变量 in
17、t * pBase;/存储第一个元素的地址 int len ; int cnt ;/当前有效元素的个数 /int increment;/自动增长因子 ;void init_arr (struct Arr *pArr, int len);bool append_arr (struct Arr *pArr,int val);/追加 bool insert_arr (struct Arr *pArr,int pos,int elem);bool delete_arr ();int get ();bool is_empty(struct Arr *pArr);bool is_full(struct A
18、rr *pArr);void sort_arr ();void show_arr (struct Arr *pArr);void inversion_arr (); int main () struct Arr arr; /已经分配好内存 ，数组没有形成 init_arr (&arr,10); /append_arr(&arr,1); if (append_arr(&arr,1) printf (追加成功n); else printf (追加失败n); /append_arr(&arr,2); if (append_arr(&arr,2) printf (追加成功n); else printf
19、 (追加失败n); /append_arr(&arr,3); if (append_arr(&arr,3) printf (追加成功n); else printf (追加失败n); /append_arr(&arr,8); if (append_arr(&arr,78) printf (追加成功n); else printf (追加失败n); if (append_arr(&arr,1000) printf (追加成功n); else printf (追加失败n); if (append_arr(&arr,188) printf (追加成功n); else printf (追加失败n); if
20、 (append_arr(&arr,89) printf (追加成功n); else printf (追加失败n); if (append_arr(&arr,8) printf (追加成功n); else printf (追加失败n); show_arr (&arr); insert_arr(&arr,2,99); show_arr (&arr); insert_arr(&arr,7,9999); show_arr (&arr); return 0;void init_arr (struct Arr *pArr, int length) pArr-pBase = (int *)malloc(s
21、izeof(int)*length); (*pArr).len = 99; if (NULL =pArr-pBase) printf (动态内存分配失败！n); exit (-1);/终止整个程序 else pArr-len = length; pArr-cnt = 0; void show_arr (struct Arr *pArr) if (is_empty(pArr) printf (数组为空！n); else for (int i = 0;icnt;+i) printf (%d,pArr-pBasei); printf(n); bool is_empty(struct Arr *pAr
22、r) if (0 = pArr-cnt) return true; else return false; bool is_full(struct Arr *pArr) if (pArr-cnt=pArr-len) return true; else return false; bool append_arr (struct Arr *pArr,int val) if (is_full(pArr) return false ; else pArr-pBasepArr-cnt = val; pArr-cnt+; return true; bool insert_arr (struct Arr *p
23、Arr,int pos,int elem ) if (pos (pArr-cnt+2)|pArr-len=pArr-cnt) printf (无法插入元素n); else for (int i = pArr-cnt-1;i = pos-1;-i ) pArr-pBasei+1 = pArr-pBasei; pArr-pBasepos-1 = elem; printf (在第%d个元素之前插入%d成功n,pos,elem); #include #include #include struct Arr/定义数据类型 ,数据类型名为struct Arr，该数据类型含有三个成员。没有定义变量 int
24、* pBase;/存储第一个元素的地址 int len ; int cnt ;/当前有效元素的个数 /int increment;/自动增长因子 ;void init_arr (struct Arr *pArr, int len);bool append_arr (struct Arr *pArr,int val);/追加 bool insert_arr (struct Arr *pArr,int pos,int elem);bool delete_arr ();int get ();bool is_empty(struct Arr *pArr);bool is_full(struct Arr
25、 *pArr);void sort_arr ();void show_arr (struct Arr *pArr);void inversion_arr (); int main () struct Arr arr; /已经分配好内存 ，数组没有形成 init_arr (&arr,100); /append_arr(&arr,1); if (append_arr(&arr,1) printf (追加成功n); else printf (追加失败n); /append_arr(&arr,2); if (append_arr(&arr,2) printf (追加成功n); else printf (追加失败n); /append_arr(&arr,3); if (append_arr(&arr,3) printf (追加成功n); else printf (追加失败n); /append_arr(&arr,8); if (append_arr(&arr,78) printf (追加成功n); else printf (追加失败n); if (append_arr(&arr,1000) printf (追加成功n); else printf (追加失败n); if (append_arr(&arr,188) printf (追加成功n); else printf (
