1 #include<stdio.h>
2 #include<malloc.h>
3 #include<stdlib.h>
4
5 //函数声明
6 PNODE create_list();//返回值是链表头结点的地址
7 void traverse_list(PNODE pHead);
8 bool is_empty(PNODE pHead);
9 int length_list(PNODE pHead);
10 bool insert_list(PNODE,int,int);
11 bool delete_list(PNODE,int,int *);
12 void sort_list(PNODE pHead);
13
14
15 typedef struct Node{
16 int data;//数据域
17 struct Node * pNext;//指针域
18 }NODE,*PNODE;//NODE等价于struct Node PNODE等价于struct Node*
19
20 int main(){
21 PNODE pHead = NULL;//等价于struct Node * pHead = NULL;
22
23 pHead = create_list();//创建一个非循环单链表,并将该链表的头结点的地址赋值给pHead
24 traverse_list(pHead);//遍历
25 sort_list(pHead);//排序
26 if(is_empty(pHead)){
27 printf("链表为空");
28 }
29 else{
30 printf("链表不空");
31 }
32
33 int len = length_list(pHead);
34 printf("链表长度是%d",len);
35
36
37
38 return 0;
39 }
40
41 PNODE create_list(){
42 int len;//有效节点的个数
43 int i;
44 int val;//临时存放用户输入的结点的值
45
46 //分配一个不存放有效数据的头结点
47 PNODE pHead = (PNODE)malloc(sizeof(NODE));
48 if(pHead==NULL){
49 printf("分配失败,程序终止");
50 exit(-1);
51 }
52
53 PNODE pTail = pHead;
54 pTail->PNext = NULL;//若只有一个结点,此时就为尾节点,指针域应当为空
55 printf("链表节点个数:");
56 scanf("%d",&len);
57
58 for(i=0;i<len;i++){
59 printf("请输入第%d个节点的值:",i+1);
60 scanf("%d",&val);
61
62 PNODE pNew = (PNODE)malloc(sizeof(NODE));//生成新结点
63 if(pNew==NULL){
64 printf("分配失败,程序终止");
65 exit(-1);
66 }
67 pNew->data = val;//把数据存放进数据域
68 pTail->pNext = pNew;//把新结点地址赋值给尾节点指针域
69 pNew->pNext = NULL;//把新结点指针域赋值为空
70 pTail = pNew;//最后一步把新结点地址复制给尾节点(就是让新结点成为尾节点)
71 // pHead->pNext = pNew;
72 // pNew->pNext=NULL;//最后一个结点的指针域为空
73 }
74 return pHead;
75 }
76
77 void traverse_list(PNODE pHead){
78 PNODE p = pHead->pNext;//若链表为空,则头结点指针域就为空,则p就为空
79
80 while(p!=NULL){
81 printf("%d ",p->data);
82 p=p->pNext;
83 }
84 printf("\n");
85 return;
86 }
87
88 bool is_empty(PNODE pHead){
89 if(pHead->pNext==NULL){//如果头结点的指针域为空,则链表为空
90 return true;
91 }
92 else{
93 return false;
94 }
95 }
96
97 int length_list(PNODE pHead){
98 PNODE p = pHead->pNext;
99 int len = 0;
100 while(p!=NULL){
101 len++;
102 p=p->pNext;
103 }
104 }
105
106 void sort_list(PNODE pHead){
107 int i ,j , t;
108 int len = length_list(pHead);
109 PNODE p,q;
110 //重点!!!
111 for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext){
112 for(j=j+1,q=p->pNext;j<len;j++,q=q->pNext){
113 if(p->data > q->data){ //类似于数组的:a[i]>a[j]
114 t = p->data; //t=a[i];
115 p->data = q->data; //a[i]=a[j];
116 q->data = t; //a[j]=t;
117 }
118 }
119 }
120
121 }
狭义的算法是与数据的存储方式密切相关
广义的算法是与数据的存储方式无关
利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的