C语言单链表实现19个功能完全详解

C语言单链表实现19个功能完全详解C语言单链表实现19个功能完全详解

C语言单链表实现19个功能完全详解
1.    #include "stdafx.h"
2.    #include "stdio.h"
3.    #include <stdlib.h>
4.    #include "string.h"
5.    typedef int elemType ;
6.    /************************************************************************/
7.    /* 以下是关于线性表链接存储（单链表）操作的18种算法 */
8.    /* 1.初始化线性表，即置单链表的表头指针为空 */
9.    /* 2.创建线性表，此函数输入负数终止读取数据*/
10.    /* 3.打印链表，链表的遍历*/
11.    /* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
12.    /* 5.返回单链表的长度 */
13.    /* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
14.    /* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
15.    /* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
16.    /* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
17.    /* 10.向单链表的表头插入一个元素 */
18.    /* 11.向单链表的末尾添加一个元素 */
19.    /* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
20.    /* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
21.    /* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
22.    /* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
23.    /* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
24.    /* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
25.    /* 18.交换2个元素的位置 */
26.    /* 19.将线性表进行快速排序 */
27.    /************************************************************************/
28.    typedef struct Node{ /* 定义单链表结点类型 */
29.    elemType element;
30.    Node *next;
31.    }Node;
32.    /* 1.初始化线性表，即置单链表的表头指针为空 */
33.    void initList(Node **pNode)
34.    {
35.    *pNode = NULL;
36.    printf("initList函数执行，初始化成功\n");
37.    }
38.    /* 2.创建线性表，此函数输入负数终止读取数据*/
39.    Node *creatList(Node *pHead)
40.    {
41.    Node *p1;
42.    Node *p2;
43.    p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
44.    if(p1 == NULL || p2 ==NULL)
45.    {
46.    printf("内存分配失败\n");
47.    exit(0);
48.    }
49.    memset(p1,0,sizeof(Node));
50.    scanf("%d",&p1->element); //输入新节点
51.    p1->next = NULL; //新节点的指针置为空
52.    while(p1->element > 0) //输入的值大于0则继续，直到输入的值为负
53.    {
54.    if(pHead == NULL) //空表，接入表头
55.    {
56.    pHead = p1;
57.    }
58.    else
59.    {
60.    p2->next = p1; //非空表，接入表尾
61.    }
62.    p2 = p1;
63.    p1=(Node *)malloc(sizeof(Node)); //再重申请一个节点
64.    if(p1 == NULL || p2 ==NULL)
65.    {
66.    printf("内存分配失败\n");
67.    exit(0);
68.    }
69.    memset(p1,0,sizeof(Node));
70.    scanf("%d",&p1->element);
71.    p1->next = NULL;
72.    }
73.    printf("creatList函数执行，链表创建成功\n");
74.    return pHead; //返回链表的头指针
75.    }
76.    /* 3.打印链表，链表的遍历*/
77.    void printList(Node *pHead)
78.    {
79.    if(NULL == pHead) //链表为空
80.    {
81.    printf("PrintList函数执行，链表为空\n");
82.    }
83.    else
84.    {
85.    while(NULL != pHead)
86.    {
87.    printf("%d ",pHead->element);
88.    pHead = pHead->next;
89.    }
90.    printf("\n");
91.    }
92.    }
93.    /* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
94.    void clearList(Node *pHead)
95.    {
96.    Node *pNext; //定义一个与pHead相邻节点
97.    if(pHead == NULL)
98.    {
99.    printf("clearList函数执行，链表为空\n");
100.    return;
101.    }
102.    while(pHead->next != NULL)
103.    {
104.    pNext = pHead->next;//保存下一结点的指针
105.    free(pHead);
106.    pHead = pNext; //表头下移
107.    }
108.    printf("clearList函数执行，链表已经清除\n");
109.    }
110.    /* 5.返回单链表的长度 */
111.    int sizeList(Node *pHead)
112.    {
113.    int size = 0;
114.    while(pHead != NULL)
115.    {
116.    size++; //遍历链表size大小比链表的实际长度小1
117.    pHead = pHead->next;
118.    }
119.    printf("sizeList函数执行，链表长度 %d \n",size);
120.    return size; //链表的实际长度
121.    }
122.    /* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
123.    int isEmptyList(Node *pHead)
124.    {
125.    if(pHead == NULL)
126.    {
127.    printf("isEmptyList函数执行，链表为空\n");
128.    return 1;
129.    }
130.    printf("isEmptyList函数执行，链表非空\n");
131.    return 0;
132.    }
133.    /* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
134.    elemType getElement(Node *pHead, int pos)
135.    {
136.    int i=0;
137.    if(pos < 1)
138.    {
139.    printf("getElement函数执行，pos值非法\n");
140.    return 0;
141.    }
142.    if(pHead == NULL)
143.    {
144.    printf("getElement函数执行，链表为空\n");
145.    return 0;
146.    //exit(1);
147.    }
148.    while(pHead !=NULL)
149.    {
150.    ++i;
151.    if(i == pos)
152.    {
153.    break;
154.    }
155.    pHead = pHead->next; //移到下一结点
156.    }
157.    if(i < pos) //链表长度不足则退出
158.    {
159.    printf("getElement函数执行，pos值超出链表长度\n");
160.    return 0;
161.    }
162.    return pHead->element;
163.    }
164.    /* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
165.    elemType *getElemAddr(Node *pHead, elemType x)
166.    {
167.    if(NULL == pHead)
168.    {
169.    printf("getElemAddr函数执行，链表为空\n");
170.    return NULL;
171.    }
172.    if(x < 0)
173.    {
174.    printf("getElemAddr函数执行，给定值X不合法\n");
175.    return NULL;
176.    }
177.    while((pHead->element != x) && (NULL != pHead->next)) //判断是否到链表末尾，以及是否存在所要找的元素
178.    {
179.    pHead = pHead->next;
180.    }
181.    if((pHead->element != x) && (pHead != NULL))
182.    {
183.    printf("getElemAddr函数执行，在链表中未找到x值\n");
184.    return NULL;
185.    }
186.    if(pHead->element == x)
187.    {
188.    printf("getElemAddr函数执行，元素 %d 的地址为 0x%x\n",x,&(pHead->element));
189.    }
190.    return &(pHead->element);//返回元素的地址
191.    }
192.    /* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
193.    int modifyElem(Node *pNode,int pos,elemType x)
194.    {
195.    Node *pHead;
196.    pHead = pNode;
197.    int i = 0;
198.    if(NULL == pHead)
199.    {
200.    printf("modifyElem函数执行，链表为空\n");
201.    }
202.    if(pos < 1)
203.    {
204.    printf("modifyElem函数执行，pos值非法\n");
205.    return 0;
206.    }
207.    while(pHead !=NULL)
208.    {
209.    ++i;
210.    if(i == pos)
211.    {
212.    break;
213.    }
214.    pHead = pHead->next; //移到下一结点
215.    }
216.    if(i < pos) //链表长度不足则退出
217.    {
218.    printf("modifyElem函数执行，pos值超出链表长度\n");
219.    return 0;
220.    }
221.    pNode = pHead;
222.    pNode->element = x;
223.    printf("modifyElem函数执行\n");
224.    return 1;
225.    }
226.    /* 10.向单链表的表头插入一个元素 */
227.    int insertHeadList(Node **pNode,elemType insertElem)
228.    {
229.    Node *pInsert;
230.    pInsert = (Node *)malloc(sizeof(Node));
231.    memset(pInsert,0,sizeof(Node));
232.    pInsert->element = insertElem;
233.    pInsert->next = *pNode;
234.    *pNode = pInsert;
235.    printf("insertHeadList函数执行，向表头插入元素成功\n");
236.    return 1;
237.    }
238.    /* 11.向单链表的末尾添加一个元素 */
239.    int insertLastList(Node **pNode,elemType insertElem)
240.    {
241.    Node *pInsert;
242.    Node *pHead;
243.    Node *pTmp; //定义一个临时链表用来存放第一个节点
244.    pHead = *pNode;
245.    pTmp = pHead;
246.    pInsert = (Node *)malloc(sizeof(Node)); //申请一个新节点
247.    memset(pInsert,0,sizeof(Node));
248.    pInsert->element = insertElem;
249.    while(pHead->next != NULL)
250.    {
251.    pHead = pHead->next;
252.    }
253.    pHead->next = pInsert; //将链表末尾节点的下一结点指向新添加的节点
254.    *pNode = pTmp;
255.    printf("insertLastList函数执行，向表尾插入元素成功\n");
256.    return 1;
257.    }
258.    /* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
259.    /* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
260.    /* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
261.    /* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
262.    /* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
263.    /* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
264.    /* 18.交换2个元素的位置 */
265.    /* 19.将线性表进行快速排序 */
266.    /******************************************************************/
267.    int main()
268.    {
269.    Node *pList=NULL;
270.    int length = 0;
271.    elemType posElem;
272.    initList(&pList); //链表初始化
273.    printList(pList); //遍历链表，打印链表
274.    pList=creatList(pList); //创建链表
275.    printList(pList);
276.    sizeList(pList); //链表的长度
277.    printList(pList);
278.    isEmptyList(pList); //判断链表是否为空链表
279.    posElem = getElement(pList,3); //获取第三个元素，如果元素不足3个，则返回0
280.    printf("getElement函数执行，位置 3 中的元素为 %d\n",posElem);
281.    printList(pList);
282.    getElemAddr(pList,5); //获得元素5的地址
283.    modifyElem(pList,4,1); //将链表中位置4上的元素修改为1
284.    printList(pList);
285.    insertHeadList(&pList,5); //表头插入元素12
286.    printList(pList);
287.    insertLastList(&pList,10); //表尾插入元素10
288.    printList(pList);
289.    clearList(pList); //清空链表
290.    system("pause");
291.    }
292.