数据结构学习2——单链表
<div id="cnblogs_post_body">顺序表的缺点：插入和删除需要进行元素的移动链表：使用节点存储数据元素，节点的地址可以连续也可以不连续
链表分为单链表/双链表/循环链表，这次只说单链表。
单链表中一个节点的组成：数据域+指针域，指针于中存放的是是一个指针，指向下一个节点的地址。
内容包括：单链表的定义/初始化/查找节点/插入节点/删除节点
先上代码：
<div class="cnblogs_code">1 #include<stdio.h>2 #include<stdlib.h>3 #include<malloc.h>4 5 //定义单链表6 struct node{7 char data;8 struct node *next;9 }; 10 typedef struct node linkList; 11 12 /*单链表结构 13 p0x804b008 14 *0x804b008 15 data'\0' 16 next0x804b018 17 *0x804b018 18 data'a' 19 next0x804b038 20 *0x804b038 21 data's' 22 nextox804b048 23 *0x804b048 24 ... 25 注：最后一个节点的next为NULL 26 */ 27 28 //初始化单链表(创建单链表) 29 linkList* linkListCreate() 30 { 31 char ch; 32 //p为创建的单链表，p2链接于p上，p1是p2与p之间的桥梁 33 linkList *p,*p1,*p2; 34 //初始化表头 35 p=(linkList*)malloc(sizeof(linkList)); 36 p->data='\0'; 37 p->next=NULL; 38 p1=p;//将p的首地址给p1，对p1的操作就是对p中元素的操作 39 while((ch=getchar())!='\n') 40 { 41 p2=(linkList*)malloc(sizeof(linkList)); 42 p2->data=ch; 43 p2->next=NULL; 44 p1->next=p2; 45 p1=p2; 46 } 47 return p;//返回链表头指针 48 } 49 50 //查找节点：按序号查找，查找链表list中第n个节点。注：链表头的下一个节点才是第一个节点 51 linkList * ElemLocatebyNum(linkList *list,int n) 52 { 53 int i=0; 54 linkList *p; 55 p=list; 56 while(p!=NULL) 57 { 58 i++; 59 p=p->next; 60 if(n==i) 61 { 62 return p; 63 } 64 } 65 return NULL; 66 } 67 68 //查找节点：按数据元素查找，查找链表list中元素为ch的节点 69 linkList * ElemLocatebyVal(linkList *list,char ch) 70 { 71 linkList *p; 72 p=list; 73 while(p!=NULL) 74 { 75 p=p->next; 76 if(ch==p->data) 77 { 78 return p; 79 } 80 } 81 return NULL; 82 } 83 84 //插入节点：在链表list的第n个节点处插入元素ch 85 void linkListInsert(linkList *list,int n,char ch) 86 { 87 linkList *p,*q; 88 p=ElemLocatebyNum(list,n-1);//链表第n-1个节点 89 if(p==NULL) 90 { 91 printf("insert error!\n"); 92 return; 93 } 94 q=(linkList*)malloc(sizeof(linkList)); 95 q->data=ch; 96 q->next=p->next; 97 p->next=q; 98 } 99 100 //删除节点：删除链表list的第n个节点101 void linkListDelete(linkList *list,int n)102 {103 linkList *p,*q;104 p=ElemLocatebyNum(list,n-1);//链表第n-1个节点105 //q=ElemLocatebyNum(list,n);//链表的第n个节点106 if(p->next==NULL || p==NULL)107 {108 printf("delete error!\n");109 return;110 }111 q=p->next;112 p->next=q->next;113 free(q);//释放第n个节点的内存空间114 }115 116 int main()117 {118 //创建链表119 linkList *p,*q;120 p=linkListCreate();121 q=p->next;//单链表的第一个节点122 printf("craete list/elment:\n");123 while(q)124 {125 printf("%c",q->data);126 q=q->next;127 }128 printf("\n");129 //查找节点：按序号130 q=ElemLocatebyNum(p,4);131 printf("find node/positon 4 elment:%c\n",q->data);132 //查找节点：按数据元素133 q=ElemLocatebyVal(p,'j');134 printf("find node/element is:%c\n",q->data);135 //插入节点136 linkListInsert(p,4,'Q');137 q=p->next;138 printf("insert node/elment:\n");139 while(q)140 {141 printf("%c",q->data);142 q=q->next;143 }144 printf("\n");145 //删除节点146 linkListDelete(p,7);147 q=p->next;148 printf("delete node/elment:\n");149 while(q)150 {151 printf("%c",q->data);152 q=q->next;153 }154 printf("\n");155 return 0;156 }
页:
[1]