首页 > 代码库 > 单链表及基本操作。（含练习）
单链表及基本操作。（含练习）
1 ////////////////////////////////////////////// 2 //单链表的初始化，建立，插入，查找，删除。 // 3 //(以及部分练习) // 4 //Author:Bread // 5 //Date: 2014.12.28 // 6 //Update 1th：2014.12.31 // 7 ////////////////////////////////////////////// 8 #include <stdio.h> 9 #include <stdlib.h> 10 typedef int ElemType; 11 //////////////////////////////////////////// 12 // 定义结点类型 // 13 //////////////////////////////////////////// 14 typedef struct Node { 15 ElemType data; //单链表中的数据域 16 short type; //结点类型:0表示结点,1表示头节点。 17 struct Node *next; //单链表的指针域 18 }Node, *LinkedList; 19 /*相当于 typedef Node* LinkedList,即LinkedList是Node的指针类型。*/ 20 21 LinkedList newnode(); //新建节点并初始化 22 LinkedList newhead(); //新建头节点并初始化 23 LinkedList LinkedListCreatH(); //头插法建立单链表 24 LinkedList LinkedListCreatT(); //尾插法建立单链表 25 LinkedList LinkedListInsert(LinkedList, int, ElemType); //在指定位置插入data = http://www.mamicode.com/x的结点 26 LinkedList LinkedListDelete(LinkedList, int); //在指定位置删除节点 27 LinkedList LinkedListDeletex(LinkedList, ElemType); //删除所有data = http://www.mamicode.com/x的结点 28 LinkedList printList(LinkedList); //输出单链表 29 LinkedList printtsiL(LinkedList); //逆序输出单链表 30 LinkedList LinkedListfree(LinkedList); //释放单链表 31 32 int main() { 33 LinkedList list, start; 34 int i; 35 ElemType x; 36 37 printf("Input data of list：\n"); 38 list = LinkedListCreatT(); 39 40 printList(list); 41 printtsiL(list); 42 43 printf("Enter the position of new node：\n"); 44 scanf("%d", &i); 45 printf("Enter the data of new node：\n"); 46 scanf("%d", &x); 47 LinkedListInsert(list, i, x); 48 49 printList(list); 50 printtsiL(list); 51 52 printf("Enter the data of node to delete：\n"); 53 scanf("%d", &x); 54 LinkedListDeletex(list, x); 55 printList(list); 56 printtsiL(list); 57 58 printf("Enter the position of node to delete：\n"); 59 scanf("%d", &i); 60 LinkedListDelete(list, i); 61 62 printList(list); 63 printtsiL(list); 64 65 LinkedListfree(list); 66 return 0; 67 } 68 69 //////////////////////////////////////////// 70 // 单链表结点的新建和初始化 // 71 //////////////////////////////////////////// 72 LinkedList newnode() { 73 Node *p; 74 p = (Node *)malloc(sizeof(Node)); //申请结点空间 75 if(p == NULL) { //判断是否有足够的内存空间 76 printf("Error: Not enough memory\n"); 77 } 78 p->data = http://www.mamicode.com/0; //初始化data 79 p->next = NULL; //初始化next 80 p->type = 0; 81 return p; 82 } 83 LinkedList newhead() { 84 Node *p; 85 p = (Node *)malloc(sizeof(Node)); //申请结点空间 86 if(p == NULL) { //判断是否有足够的内存空间 87 printf("Error: Not enough memory\n"); 88 } 89 p->data = http://www.mamicode.com/0; //初始化data 90 p->next = NULL; //初始化next 91 p->type = 1; 92 return p; 93 94 } 95 //////////////////////////////////////////// 96 // 单链表的建立1，头插法建立单链表 // 97 //////////////////////////////////////////// 98 LinkedList LinkedListCreatH() { 99 Node *L, *p;100 L = newhead(); //申请头结点空间 101 ElemType x; //x为链表中的数据 102 while(scanf("%d", &x) != EOF) { //#define EOF (-1) 在DOS下 键入Ctrl+Z(^Z) 在Linux下 键入Ctrl+D103 p = newnode(); //申请新的结点 104 p->data = http://www.mamicode.com/x; //结点数据域赋值 105 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL 106 L->next = p;107 }108 109 return L;110 }111 //////////////////////////////////////////// 112 // 单链表的建立2，尾插法建立单链表 //113 ////////////////////////////////////////////114 LinkedList LinkedListCreatT() {115 Node *L, *p, *r;116 L = newhead(); //申请头结点空间 117 r = L; //r始终指向终端结点，开始时指向头结点 118 ElemType x; //x为链表中的数据 119 while(scanf("%d", &x) != EOF) {120 p = newnode(); //申请新的结点 121 p->data = http://www.mamicode.com/x; //结点数据域赋值 122 r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL 123 r = p;124 }125 r->next = NULL;126 127 return L;128 }129 //////////////////////////////////////////// 130 //单链表的插入，在链表的第i个位置插入x的元素 // /*含练习*/131 ////////////////////////////////////////////132 LinkedList LinkedListInsert(LinkedList L, int i, ElemType x) {133 Node *pre = L, *p; //pre为前驱结点 134 int tempi = 0;135 for(tempi = 1; tempi < i && pre->next != NULL; tempi++) {136 pre = pre->next; //查找第i个位置的前驱结点 137 }138 /*练习：越界错误信息*/139 //插入的结点为p140 p = newnode();141 p->data =http://www.mamicode.com/ x;142 p->next = pre->next;143 pre->next = p;144 145 return L;146 }147 //////////////////////////////////////////// 148 // 单链表的删除1，在链表中删除所有值为x的元素 //149 // 单链表的删除2，在链表中删除第i个元素 // /*含练习*/150 ////////////////////////////////////////////151 LinkedList LinkedListDeletex(LinkedList L, ElemType x) {152 Node *p = L, *pre = NULL; //pre为前驱结点，p为查找的结点。 153 while(p != NULL) { //查找值为x的元素 154 if(p->data =http://www.mamicode.com/= x && pre == NULL) {155 L = p->next; //删除操作，将其前驱next指向其后继。 156 free(p);157 p = L;158 continue;159 }160 else if(p->data =http://www.mamicode.com/= x) {161 pre->next = p->next; //删除操作，将其前驱next指向其后继。 162 free(p);163 p = pre;164 }165 pre = p;166 p = p->next;167 }168 169 return L;170 }171 LinkedList LinkedListDelete(LinkedList L, int i) {172 Node *pre = L, *p; //pre为前驱结点 173 int tempi = 0;174 for(tempi = 1; tempi < i && pre->next != NULL; tempi++) {175 pre = pre->next; //查找第i个位置的前驱结点 176 }177 /*练习：越界错误信息*/178 p = pre->next;179 pre->next = p->next;180 free(p);181 return L;182 }183 //////////////////////////////////////////// 184 // 单链表的顺逆序输出 // /*含练习*/185 ////////////////////////////////////////////186 LinkedList printList(LinkedList L) {187 Node *p = L->next;188 printf("Now List:");189 /*练习：链表顺序输出*/190 printf("\n");191 return L;192 }193 LinkedList printtsiL(LinkedList L) { //练习：改成栈结构实现194 if(L != NULL) {195 printtsiL(L->next);196 if(!L->type) {197 printf("%d ", L->data);198 }199 else {200 printf("\n");201 }202 }203 return NULL;204 }205 //////////////////////////////////////////// 206 // 单链表的释放 // /*练习*/207 ////////////////////////////////////////////208 LinkedList LinkedListfree(LinkedList L) {209 /*自己写*/210 return L;211 }
单链表及基本操作。（含练习）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。