2022年数据结构笔记归类 .pdf

《2022年数据结构笔记归类 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构笔记归类 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构笔记1 1.线性表文件结构list.h 1./list.h 2.3.#ifndef _LIST_H 4.#define _LIST_H /条件编译语句5.6.#define LIST_INIT_SIZE 10 /线性表初始大小7.#define LIST_INCREMENT 10 /递增大小8.9.typedefstruct10. 11. ElemType * elem; / 线性表首地址12.int length; / 线性表当前使用长度13.int size; / 线性表当前最大长度14.LIST; 15.16.LIST *InitList(); / 初始化17.void Free

2、List(LIST *l); 18.int InsertList(LIST* l,int i,ElemType *e); 19.int DeleteList(LIST *l,int i); 20.21.#endiflist.c 1./list.c 2.#include 3.#include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 4.#include stu.h 5.#include list.h 6.7./ 初始线性

3、表函数8.LIST * InitList() 9. 10. LIST* l=(LIST*)malloc(sizeof(LIST); 11./在堆中动态定义一个线性表结构指针12.if(l=NULL) 13. 14. exit(0); 15. 16.17. l-elem=(ElemType*)malloc(LIST_INIT_SIZE* sizeof(ElemType); 18./在堆中动态开辟数据空间19.if(l-elem=NULL) 20. 21. free(l); 22. exit(0); 23. 24. l-length=0; 25. l-size=LIST_INIT_SIZE; 26

4、.return l; 27. 28.29.void FreeList(LIST *l) 30. 31. free(l-elem); / 释放线性表的成员空间32. free(l); /释放线性表本身33. 34.35.int InsertList(LIST* l,int i,ElemType *e) 36. 37. ElemType *p=NULL,*q=NULL,*newElem=NULL; 38.if(l=NULL|e=NULL) 39.return 0; 40.if(il-length+1) 41.return 0; 42.if(l-length=l-size) 43. 44. newE

5、lem=realloc(l-elem, 45. (l-size+LIST_INCREMENT)*sizeof(ElemType); 46.if(newElem=NULL) 47.return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 48. l-elem=newElem; 49. l-size+=LIST_INCREMENT; 50. 51.52. q=&l-elemi-1; /要插入的位置53.for(p=&(l

6、-eleml-length-1);p=q;p-) 54. *(p+1)=*p; / 将 p 往后移一位55. *q=*e; /插入56. +l-length; 57.return 1; 58. 59.60.int DeleteList(LIST *l,int i) 61. 62. ElemType *p=NULL,*q=NULL; 63.if(l=NULL) 64.return 0; 65.if(il-length) 66.return 0; 67. p=&l-elemi-1; 68. q=&l-eleml-length-1; 69.for(;plength; 72.return 1; 73.

7、 stu.h 1./stu.h 2.3.#ifndef _STU_H 4.#define _STU_H 5.6.typedefstruct/定义一个学生的结构体7. 8.char sno5; 9.char name21; 10.char sex3; 11.int score; 12.ElemType; 13.14.#endif名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - main.c 1./main.c 2.#include

8、 3.#include stu.h 4.#include list.h 5.6.ElemType stu3= 7. s010, 张三 , 男 ,80, 8. s011, 张四 , 男 ,81, 9. s012, 张五 , 男 ,82 10.; 11.12.void main() 13. 14./定义一个线性性表指针15.int i; 16. LIST* list=NULL; 17. list=InitList(); / 初始化线性表18.19.for(i=0;i3;i+) 20. InsertList(list,1,&stui); 21. DeleteList(list,2); 22.23.

9、FreeList(list); 24. 2.单链表文件结构list.h 1./list.h 2.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 3.#ifndef _LIST_H 4.#define _LIST_H 5.6.typedefstruct _node 7. /结点类型定义8.void *data; /结点的数据域9.struct _node *next; / 结点的指针域10.NODE; 11.12.typedef

10、struct13. /链表类型定义14. NODE * head;/头结点15. NODE * last;/尾结点16.int length;/ 链表长度17.LIST; 18.19.LIST* InitList(); 20.int AddNode(LIST* l,void *data,int size); 21.NODE* FindNodeByKey(LIST *l,void *key, 22.int (*compare)(void *, void*) /* 函数指针 */ ); 23.NODE* FindNode(LIST *l,void *key, 24.int (*compare)(v

11、oid *, void*) /* 函数指针 */ ,NODE *pre); 25.int DeleteListByKey(LIST* l,void * Key,int (*compare)(void*, void*); 26.27.#endiflist.c 1./list.c 2.3.#include 4.#include 5.#include 6.#include list.h 7.8.LIST* InitList() 9. 10. LIST* l=(LIST*)malloc(sizeof(LIST); / 创建一个链表11.if(l=NULL) 12. exit(0); 13. memse

12、t(l,0,sizeof(LIST);/ 将链表清零14.return l; 15. 16.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 17.int AddNode(LIST* l,void *data,int size) /添加结点18. 19./在调试中可以这样看结点的值(struct STU*)l-head-data,(struct STU*)l-last-data 20. NODE *n=NULL; 21.if(l

13、=NULL|data=NULL) 22.return 0; 23. n=(NODE*)malloc(sizeof(NODE); / 创建一个结点24.if(n=NULL) 25.return 0; 26. n-data=data; 27. n-data=malloc(size); 28.if(n-next=NULL) 29. 30. free(n); 31.return 0; 32. 33. memcpy(n-data,data,size);/ 把数据拷到目标结点中去34.35./*/方法一36. if(l-head=NULL) 37. 38. l-head=n; 39. l-last=n;

14、40. l-length=1; 41. 42. else 43. 44. l-last-next=n;/挂在尾结点后面45. l-last=n; /改变尾结点的指向46. l-length+; 47. 48. */49./方法二50.if(l-head=NULL) 51. l-head=n; 52.else53. l-last-next=n; 54. l-last=n; 55. l-length+; 56.return 1; 57. 58.59.NODE* FindNodeByKey(LIST *l,void *key, 60.int (*compare)(void *, void*) /*

15、函数指针 */ ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 61. /查找结点62. NODE *p=NULL; 63.if(l=NULL|key=NULL|compare=NULL) 64.return NULL; 65. p=l-head;/ 让 p 指向第一个结点66.while(p) 67. 68.if(compare(p-data,key)=1)/ 如果返回为1 说明找到了69.return p; 70. p

16、=p-next;/ 否则继续往下找71. 72.return NULL;/都没找到，返回空73. 74.75.76.NODE* FindNode(LIST *l,void *key, 77.int (*compare)(void *, void*) /* 函数指针 */ ,NODE *pre) 78. /查找结点 , 并传入前一个结点的参数79. NODE *p=NULL; 80.if(l=NULL|key=NULL|compare=NULL|pre=NULL) 81.return NULL; 82. p=l-head;/ 让 p 指向第一个结点83. *pre=NULL; 84.while(

17、p) 85. 86.if(compare(p-data,key)=1)/ 如果返回为1 说明找到了87.return p; 88. *pre=p;/ 找到的结点的前一个结点89. p=p-next;/ 否则继续往下找90. 91.return NULL;/都没找到，返回空92. 93.94.int DeleteListByKey(LIST* l,void * key,int (*compare)(void*, void*) 95. /删除结点96. NODE *p=NULL,*q=NULL; 97. p=FindNode(l,key,compare,&q/* 前一个结点的地址*/ ); 98.

18、if(p=NULL) 99.return 0; 100.if(q=NULL)/ 如果前一个结点为空101. l-head=p-next;/ 那么将头指针指向要删除的结点的后一个结点102.else103. q-next=p-next; 104.if(p=l-last) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - 105. l-last=q; 106. free(p-data); 107. free(p); 108. l-l

19、ength-; 109.return 1; 110. main.c 1./main.c 2.3.#include 4.#include 5.#include list.h 6.7.struct STU 8. 9.char sno5; 10.char name21; 11.int age; 12.float score; 13.s3= 14. s001, lin wu,12,90, 15. s002, xiao ming,13,91, 16. s003, wang wu,11,100 17.; 18.19.int CompareByName(void *info,void *key) 20. 2

20、1.struct STU* stu=(struct STU*)info; 22.char *name=(char *)key; 23.return strcmp(stu-name,name)=0?1:0; 24. 25.26.int CompareBySno(void *info,void *key) 27. 28.struct STU* stu=(struct STU*)info; 29.char *sno=(char *)key; 30.return strcmp(stu-sno,sno)=0?1:0; 31. 32.33.void main() 34. 35.int i; 名师资料总结

21、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 36. NODE *res=NULL;/ 存放找到的结果37.char name=xiao ming,sno=s001; 38. LIST* list=InitList(); 39.for(i=0;ihead-data,(struct STU*)list-last-data 51.else52. printf(delete failn); 53.3.双链表文件结构list.h 1./list.

22、h 2.3.#ifndef _LIST_H 4.#define _LIST_H 5.6.typedefstruct _node 7. 8.void *data; 9.struct _node *pior; 10.struct _node *next; 11.NODE; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 12.13.typedefstruct14. 15. NODE *head; 16. NODE *last; 1

23、7.int length; 18.LIST; 19.20.LIST *InitList(); 21.int InsertNode(LIST *l,void *data,int size); 22.int DeletNode(LIST* l,int n); 23.void PrintList(LIST *l,int page,int perp,void(*printNode)(void*); 24.void ClearList(LIST* l); 25.void DestroyList(LIST *l); 26.27.28.#endiflist.c 1./list.c 2.3.#include

24、4.#include 5.#include 6.#include list.h 7.8.LIST *InitList()/初始化链表9. 10. LIST *l=(LIST*)malloc(sizeof(LIST); 11.if(l=NULL) exit(0); 12. l-head=(NODE*)malloc(sizeof(NODE); 13.if(l-head=NULL) exit(0); 14. memset(l-head,0,sizeof(NODE); 15. l-last=(NODE*)malloc(sizeof(NODE); 16.if(l-last=NULL) exit(0);

25、17. memset(l-last,0,sizeof(NODE); 18.19./l-head-pior=NULL; 20. l-head-next=l-last;/将头结点的后续指向尾结点21. l-last-pior=l-head;/将尾结点的前驱指向头结点22.23. l-length=0; 24.return l; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 25. 26.27.int InsertNode(LI

26、ST *l,void *data,int size) / 插入结点28. 29. NODE *n=NULL; / 定义一个空结点30.if(l=NULL|data=NULL|sizedata=malloc(size);/ 为结点的数据域分配空间36.if(n-data=NULL) 37. 38. free(n); 39.return 0; 40. 41. memcpy(n-data,data,size);/ 将传入的数据拷贝到结点的数据域当中42. n-next=l-last; / 它的后继指针指向尾结点43. n-pior=l-last-pior; / 它的前驱指针指向尾结点的前一个44.4

27、5. l-last-pior-next=n; / 把尾结点的前一个的后继指针指向它46. l-last-pior=n; / 把尾结点前驱指针指向它47. l-length+; / 链表的长度加1 48.return 1; 49. 50.51.int DeletNode(LIST* l,int n) / 删除结点52. 53. NODE *p=NULL; 54.int i=0; 55.if(l=NULL|nl-length)/ 判断传入的参数是否合法56.return 0; 57. p=l-head-next;/ 将 p 指向头结点的下一个58.while(ilength)/查找第 n 个结点5

28、9. 60. i+; 61.if(i=n) 62.break; 63. p=p-next; 64. 65. p-pior-next=p-next;/将 p 的前一个的后继指针指向p 的后一个66. p-next-pior=p-pior;/将 p 的后一个的前驱指针指向p 的前一个67. free(p-data);/ 释放 p 结点的数据域68. free(p);/释放 p 结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - -

29、69. l-length-; 70.return 1; 71. 72.73.void PrintList(LIST *l,int page,int perP,void(*printNode)(void*)/分布打印链表中的数据74. /page为页的编号， perP为每页的结点数75.int start,end,i; 76. NODE *p=NULL; 77.if(l=NULL|printNode=NULL)/判断传入的参数是否有效78.return; 79. start=(page-1)*perP+1;/将在某页面第一条要打印的数据所对映的结点所在链表中的位置80. end=page*per

30、P;/ 将在某页面最后一条要打印的数据所对映的结点所在链表中的位置81. p=l-head-next;/ 将 p 指向第一个数据结点82. i=0; 83.while(ilength & p-next!=NULL) 84. 85. i+; 86.if(i=start) break; / 定位到某页面的第一条要打印的数据87. p=p-next; 88. 89.for(;inext!=NULL;i+)/ 打印某一页面的数据，直到最后一条90. 91. printNode(p-data); 92. p=p-next; 93. 94. 95.96.void ClearList(LIST* l)/ 清

31、空链表97. 98. NODE *p=NULL; 99.if(l=NULL) 100.return; 101./* 102. /方法一103. while(l-length) 104. DeleteNode(l,1); 105. */106.107./ 方法二108.while(l-length) 109. 110. p=l-head-next;/ 把 p 指向第一数据结点111. l-head-next=p-next;/把头结点的前驱指针指向p 的下一个 ( 第一个数据结点) 112. p-next-pior=l-head;/把 p 的下一个的前驱指针指向头结点名师资料总结 - - -精品资

32、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 113. free(p-data);/释放 p 指向的结点的数据域114. free(p);/ 释放 p 结点115. l-length-;/链表长度减1 116. 117. 118.119.void DestroyList(LIST *l)/ 删除链表120. 121. LIST *p=*l; 122./ 定义一个指向链表l 的 p 指针 , 并将传入的指向链表的指针变量的值*l,即(*&list)赋给它

33、123./ 这里指向链表的指针变量的值*l是链表的地址124.if(p=NULL) return; 125. ClearList(p);/ 清空链表126. free(p-head);/ 释放头结点127. free(p-last);/ 释放尾结点128. free(p);/释放指针变量129./p=NULL; 130. *l=NULL;/将指向链表的指针的值赋成空值，即将指向已经销毁了的链表的指针指向空值131. main.c 1./main.c 2.3.#include 4.#include list.h 5.6.double d5=10.23,34.23,54.65,122,35.5;

34、7.8.void PrintData(void *data)/打印数据9. 10.double *d=(double*)data; 11. printf(d=%lfn,*d); 12. 13.14.void main() 15. 16.int i; 17. LIST *list=InitList(); 18.for(i=0;i5;i+) 19. InsertNode(list,&di,sizeof(di); 20. PrintList(list,1,3,PrintData); 21.22. DestroyList(&list);/ 删除链表名师资料总结 - - -精品资料欢迎下载 - - -

35、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 23./&list 传递指向链表的指针变量地址给DestroyList函数24.if(list=NULL) 25. printf(list is NULLn); 26.else27. printf(list is not NULLn); 28.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -