数据结构 链表基础算法

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 typedef struct node
  5 {
  6 int data;
  7 struct node * pNext;
  8 }NODE,* PNODE;
  9 //节点定义
 10 //函数声明
 11 PNODE create_list();
 12 void traverse_list(PNODE);
 13 int len_list(PNODE);
 14 void sort_list(PNODE);
 15 void delete_list(PNODE);
 16 void insert_list(PNODE);
 17 void update_list(PNODE);
 18 //函数声明结束
 19 int main(void)
 20 {
 21     PNODE pHead=create_list();
 22     traverse_list(pHead);
 23     sort_list(pHead);
 24     delete_list(pHead);
 25     insert_list(pHead);
 26     update_list(pHead);
 27     return 0;
 28 }
 29 PNODE create_list()
 30 {
 31     int len,val,i;
 32     printf("请输入链表的长度 len=");
 33     scanf("%d",&len);
 34     PNODE phead=(PNODE)malloc(sizeof(NODE));
 35     if(phead==NULL)
 36     {
 37         printf("内存分配失败");
 38         exit(-1);
 39     }
 40     PNODE ptail=phead;
 41     ptail->pNext=NULL;
 42     for(i=0;i<len;i++)
 43     {
 44         PNODE pnew=(PNODE)malloc(sizeof(NODE));
 45         if(pnew==NULL)
 46         {
 47         printf("内存分配失败");
 48         exit(-1);
 49         }
 50         printf("请输入第%d个节点的值",i+1);
 51         scanf("%d",&val);
 52         pnew->data=val;
 53         ptail->pNext=pnew;
 54         pnew->pNext=NULL;
 55         ptail=pnew;
 56     }
 57 return phead;
 58 }            //创建初始化链表
 59 void traverse_list(PNODE phead)
 60 {
 61     PNODE p=phead->pNext;
 62     while(p!=NULL)
 63     {
 64     printf("%d\t",p->data);
 65     p=p->pNext;
 66     }
 67     printf("\n");
 68 }        //遍历链表
 69 int len_list(PNODE phead)
 70 {
 71     PNODE p=phead->pNext;
 72     int len=0;
 73     while(p!=NULL)
 74     {
 75     p=p->pNext;
 76     len++;
 77     }
 78     return len;
 79 }            //链表元素个数
 80 void sort_list(PNODE phead)
 81 {
 82     int i=0,j=0,t;
 83     int len=len_list(phead);
 84     PNODE p,q;
 85 for(p=phead->pNext;i<len-1;i++,p=p->pNext)
 86 {
 87     for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
 88     {
 89         if(p->data<q->data)
 90         {
 91         t=p->data;
 92         p->data=q->data;
 93         q->data=t;
 94         }
 95     }
 96 }
 97     printf("排序后\n");
 98     traverse_list(phead);
 99 }        // 冒泡排序
100 
101 void delete_list(PNODE phead)
102 {
103     int i=0,pos;
104     PNODE p=phead;
105     printf("请输入要删除的值的位置:");
106     scanf("%d",&pos);
107 while(p->pNext!=NULL&&i<pos-1)
108 {
109     p=p->pNext;
110     i++;
111 }
112 if(p->pNext==NULL||i>pos-1)
113 {
114     printf("输入位置有误\n");
115     delete_list(phead);
116     return;
117 }
118 PNODE q=p->pNext;
119 p->pNext=p->pNext->pNext;
120 printf("删除%d成功\n",q->data);
121 free(q);
122 q=NULL;
123 traverse_list(phead);
124 }        //删除指定节点
125 
126 void insert_list(PNODE phead)
127 {
128     int pos,i=0;
129     PNODE p=phead;
130     printf("请输入要插入的位置:");
131     scanf("%d",&pos);
132     while(p->pNext!=NULL&&i<pos-1)
133     {
134         p=p->pNext;
135         i++;
136     }
137     if(p->pNext==NULL||i>pos-1) 
138     {
139         printf("输入位置有误\n");
140         insert_list(phead);
141         return;
142     }
143         PNODE pnew=(PNODE)malloc(sizeof(NODE));
144         if(pnew==NULL) 
145         {
146             printf("内存分配失败");
147             exit(-1);
148         }
149         int data;
150         printf("请输入要插入的数值:");
151         scanf("%d",&data);
152         pnew->data=data;
153         pnew->pNext=p->pNext;
154         p->pNext=pnew;
155         traverse_list(phead);
156 }        //在指定位置插入节点
157 
158 void update_list(PNODE phead)
159 {
160 int pos,i=0;
161 PNODE p=phead;
162 printf("请输入要修改的位置:");
163 scanf("%d",&pos);
164 while(p->pNext!=NULL&&i<pos-1)
165 {
166 p=p->pNext;
167 i++;
168 }
169 if(p->pNext==NULL||i>pos-1)
170 {
171 printf("位置输入有误，请从输入\n");
172 update_list(phead);
173 return;
174 }
175 int val;
176 printf("请输入修改后的值:");
177 scanf("%d",&val);
178 printf("修改成功,%d修改为",p->pNext->data);
179 p->pNext->data=val;
180 printf("%d\n",val);
181 traverse_list(phead);
182 } //修改具体位置节点的值