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

C语言单链表实现19个功能完全详解最近在复习数据结构，想把数据结构里面涉及的都自己实现一下，完全是用C语言实现的。自己编写的不是很好，大家可以参考，有错误希望帮忙指正，现在正处于编写阶段，一共将要实现19个功能。到目前我只写了一半，先传上来，大家有兴趣的可以帮忙指正，谢谢在vs2010上面编译运行无错误。每天都会把我写的新代码添加到这个里面。直到此链表完成。#include stdafx.h#include stdio.h#include #include string.htypedefintelemType ;/*/* 以下是关于线性表链接存储（单链表）操作的18种算法 */* 1.初始化线性表，即置单链表的表头指针为空 */* 2.创建线性表，此函数输入负数终止读取数据*/* 3.打印链表，链表的遍历*/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */* 5.返回单链表的长度 */* 6.检查单链表是否为空，若为空则返回，否则返回 */* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回，否则返回 */* 10.向单链表的表头插入一个元素 */* 11.向单链表的末尾添加一个元素 */* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回，否则返回 */* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */* 18.交换2个元素的位置 */* 19.将线性表进行快速排序 */*/typedefstructNode /* 定义单链表结点类型 */elemType element;Node *next;Node;/* 1.初始化线性表，即置单链表的表头指针为空 */voidinitList(Node *pNode)*pNode = NULL;printf(initList函数执行，初始化成功n);/* 2.创建线性表，此函数输入负数终止读取数据*/Node *creatList(Node *pHead)Node *p1;Node *p2;p1=p2=(Node *)malloc(sizeof(Node); /申请新节点if(p1 = NULL | p2 =NULL)printf(内存分配失败n);exit(0);memset(p1,0,sizeof(Node);scanf(%d,&p1-element); /输入新节点p1-next = NULL; /新节点的指针置为空while(p1-element 0) /输入的值大于0则继续，直到输入的值为负if(pHead = NULL) /空表，接入表头pHead = p1;elsep2-next = p1; /非空表，接入表尾p2 = p1;p1=(Node *)malloc(sizeof(Node); /再重申请一个节点if(p1 = NULL | p2 =NULL)printf(内存分配失败n);exit(0);memset(p1,0,sizeof(Node);scanf(%d,&p1-element);p1-next = NULL;printf(creatList函数执行，链表创建成功n);returnpHead; /返回链表的头指针/* 3.打印链表，链表的遍历*/voidprintList(Node *pHead)if(NULL = pHead) /链表为空printf(PrintList函数执行，链表为空n);elsewhile(NULL != pHead)printf(%d ,pHead-element);pHead = pHead-next;printf(n);/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */voidclearList(Node *pHead)Node *pNext; /定义一个与pHead相邻节点if(pHead = NULL)printf(clearList函数执行，链表为空n);return;while(pHead-next != NULL)pNext = pHead-next;/保存下一结点的指针free(pHead);pHead = pNext; /表头下移printf(clearList函数执行，链表已经清除n);/* 5.返回单链表的长度 */intsizeList(Node *pHead)intsize = 0;while(pHead != NULL)size+; /遍历链表size大小比链表的实际长度小1pHead = pHead-next;printf(sizeList函数执行，链表长度 %d n,size);returnsize; /链表的实际长度/* 6.检查单链表是否为空，若为空则返回，否则返回 */intisEmptyList(Node *pHead)if(pHead = NULL)printf(isEmptyList函数执行，链表为空n);return1;printf(isEmptyList函数执行，链表非空n);return0;/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */elemType getElement(Node *pHead, intpos)inti=0;if(pos next; /移到下一结点if(i element;/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */elemType *getElemAddr(Node *pHead, elemType x)if(NULL = pHead)printf(getElemAddr函数执行，链表为空n);returnNULL;if(x element != x) & (NULL != pHead-next) /判断是否到链表末尾，以及是否存在所要找的元素pHead = pHead-next;if(pHead-element != x) & (pHead != NULL)printf(getElemAddr函数执行，在链表中未找到x值n);returnNULL;if(pHead-element = x)printf(getElemAddr函数执行，元素 %d 的地址为 0x%xn,x,&(pHead-element);return&(pHead-element);/返回元素的地址/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回，否则返回 */intmodifyElem(Node *pNode,intpos,elemType x)Node *pHead;pHead = pNode;inti = 0;if(NULL = pHead)printf(modifyElem函数执行，链表为空n);if(pos next; /移到下一结点if(i element = x;printf(modifyElem函数执行n);return1;/* 10.向单链表的表头插入一个元素 */intinsertHeadList(Node *pNode,elemType insertElem)Node *pInsert;pInsert = (Node *)malloc(sizeof(Node);memset(pInsert,0,sizeof(Node);pInsert-element = insertElem;pInsert-next = *pNode;*pNode = pInsert;printf(insertHeadList函数执行，向表头插入元素成功n);return1;/* 11.向单链表的末尾添加一个元素 */intinsertLastList(Node *pNode,elemType insertElem)Node *pInsert;Node *pHead;Node *pTmp; /定义一个临时链表用来存放第一个节点pHead = *pNode;pTmp = pHead;pInsert = (Node *)malloc(sizeof(Node); /申请一个新节点memset(pInsert,0,sizeof(Node);pInsert-element = insertElem;while(pHead-next != NULL)pHead = pHead-next;pHead-next = pInsert; /将链表末尾节点的下一结点指向新添加的节点*pNode = pTmp;printf(insertLastList函数执行，向表尾插入元素成功n);return1;/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回，否则返回 */* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */* 18.交换2个元素的位置 */* 19.将线性表进行快速排序 */*/intmain()Node *pList=NULL;intlength = 0;elemType posElem;initList(&pList); /链表初始化printList(pList); /遍历链表，打印链表pList=creatList(pList); /创建链表printList(pList);sizeList(pList); /链表的长度printList(pList);isEmptyList(pList); /判断链表是否为空链表posElem = getElement(pList,3); /获取第三个元素，如果元素不足3个，则返回0printf(getElement函数执行，位置 3 中的元素为 %dn,posElem); printList(pL