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

blake · 发表于 2017-9-2 09:25:50

#include <stdio.h>
#include <stdlib.h>
#define NN 12
#define MM 20
typedef int elemType ;
/************************************************************************/
/* 以下是关于线性表链接存储（单链表）操作的18种算法 */
/* 1.初始化线性表，即置单链表的表头指针为空*/
/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/
/* 3.返回单链表的长度*/
/* 4.检查单链表是否为空，若为空则返回1，否则返回0 */
/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/
/* 6.遍历一个单链表*/
/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回1，否则返回0 */
/* 9.向单链表的表头插入一个元素*/
/* 10.向单链表的末尾添加一个元素*/
/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回0 */
/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序*/
/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/
/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/
/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/
/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
/* 17.交换2个元素的位置*/
/* 18.将线性表进行快速排序*/
/************************************************************************/
struct sNode{ /*定义单链表结点类型*/
elemType data;
struct sNode *next;
};
/* 1.初始化线性表，即置单链表的表头指针为空*/
void initList(struct sNode* *hl)
{
*hl = NULL;
return;
}
/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/
void clearList(struct sNode* *hl)
{
/* cp和np分别作为指向两个相邻结点的指针*/
struct sNode *cp, *np;
cp = *hl;
/*遍历单链表，依次释放每个结点*/
while(cp != NULL){
np = cp->next; /*保存下一个结点的指针*/
free(cp);
cp = np;
}
*hl = NULL; /*置单链表的表头指针为空*/
return;
}
/* 3.返回单链表的长度*/
int sizeList(struct sNode *hl)
{
int count = 0; /*用于统计结点的个数*/
while(hl != NULL){
count++;
hl = hl->next;
}
return count;
}
/* 4.检查单链表是否为空，若为空则返回１，否则返回０*/
int emptyList(struct sNode *hl)
{
if(hl == NULL){
return 1;
}else{
return 0;
}
}
/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/
elemType getElem(struct sNode *hl, int pos)
{
int i = 0; /*统计已遍历的结点个数*/
if(pos < 1){
printf("pos值非法，退出运行！");
exit(1);
}
while(hl != NULL){
i++;
if(i == pos){
break;
}
hl = hl->next;
}
if(hl != NULL){
return hl->data;
}else{
printf("pos值非法，退出运行！");
exit(1);
}
}
/* 6.遍历一个单链表*/
void traverseList(struct sNode *hl)
{
while(hl != NULL){
printf("%5d", hl->data);
hl = hl->next;
}
printf(" ");
return;
}
/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
elemType* findList(struct sNode *hl, elemType x)
{
while(hl != NULL){
if(hl->data == x){
return &hl->data;
}else{
hl = hl->next;
}
}
return NULL;
}
/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０*/
int updatePosList(struct sNode *hl, int pos, elemType x)
{
int i = 0;
struct sNode *p = hl;
while(p != NULL){ /*查找第pos个结点*/
i++;
if(pos == i){
break;
}else{
p = p->next;
}
}
if(pos == i){
p->data = x;
return 1;
}else{
return 0;
}
}
/* 9.向单链表的表头插入一个元素*/
void insertFirstList(struct sNode* *hl, elemType x)
{
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf("内存分配失败，退出运行！");
exit(1);
}
newP->data = x; /*把x的值赋给新结点的data域*/
/*把新结点作为新的表头结点插入*/
newP->next = *hl;
*hl = newP;
return;
}
/* 10.向单链表的末尾添加一个元素*/
void insertLastList(struct sNode* *hl, elemType x)
{
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf("内在分配失败，退出运行！");
exit(1);
}
/*把x的值赋给新结点的data域，把空值赋给新结点的next域*/
newP->data = x;
newP->next = NULL;
/*若原表为空，则作为表头结点插入*/
if(*hl == NULL){
*hl = newP;
}
/*查找到表尾结点并完成插入*/
else{
struct sNode *p = NULL;
while(p->next != NULL){
p = p->next;
}
p->next = newP;
}
return;
}
/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０*/
int insetPosList(struct sNode* *hl, int pos, elemType x){
int i = 0;
struct sNode *newP;
struct sNode *cp = *hl, *ap = NULL;
/*对pos值小于等于０的情况进行处理*/
if(pos <= 0){
printf("pos值非法，返回０表示插入失败！");
return 0;
}
/*查找第pos个结点*/
while(cp != NULL){
i++;
if(pos == i){
break;
}else{
ap = cp;
cp = cp->next;
}
}
/*产生新结点，若分配失败，则停止插入*/
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf("内存分配失败，无法进行插入操作！");
return 0;
}
/*把x的值赋给新结点的data域*/
newP->data = x;
/*把新结点插入到表头*/
if(ap == NULL){
newP->next = cp; /*或改为newP->next = *hl; */
*hl = newP;
}
/*把新结点插入到ap和cp之间*/
else{
newP->next = cp;
ap->next = newP;
}
return 1; /*插入成功返回1 */
}
/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序*/
void insertOrderList(struct sNode* *hl, elemType x)
{
/*把单链表的表头指针赋给cp，把ap置空*/
struct sNode *cp = *hl, *ap = NULL;
/*建立新结点*/
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf("内在分配失败，退出运行！");
exit(1);
}
newP->data = x; /*把x的值赋给新结点的data域*/
/*把新结点插入到表头*/
if((cp == NULL) || (x < cp->data)){
newP->next = cp;
*hl = newP;
return;
}
/*顺序查找出x结点的插入位置*/
while(cp != NULL){
if(x < cp->data){
break;
}else{
ap = cp;
cp = cp->next;
}
}
/*把x结点插入到ap和cp之间*/
newP->next = cp;
ap->next = newP;
return;
}
/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/
elemType deleteFirstList(struct sNode* *hl)
{
elemType temp;
struct sNode *p = *hl; /*暂存表头结点指针，以便回收*/
if(*hl == NULL){
printf("单链表为空，无表头可进行删除，退出运行！");
exit(1);
}
*hl = (*hl)->next; /*使表头指针指向第二个结点*/
temp = p->data; /*暂存原表头元素，以便返回*/
free(p); /*回收被删除的表头结点*/
return temp; /*返回第一个结点的值*/
}
/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/
elemType deleteLastList(struct sNode* *hl)
{
elemType temp;
/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/*单链表为空则停止运行*/
if(cp == NULL){
printf("单链表为空，无表头进行删除，退出运行！");
exit(1);
}
/*从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点*/
while(cp->next != NULL){
ap = cp;
cp = cp->next;
}
/*若单链表中只有一个结点，则需要修改表头指针*/
if(ap == NULL){
*hl = (*hl)->next; /*或改为*hl = NULL; */
}
/*删除表尾结点*/
else{
ap->next = NULL;
}
/*暂存表尾元素，以便返回*/
temp = cp->data;
free(cp); /*回收被删除的表尾结点*/
return temp; /*返回表尾结点的值*/
}
/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/
elemType deletePosList(struct sNode* *hl, int pos)
{
int i = 0;
elemType temp;
/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/*单链表为空或pos值非法则停止运行*/
if((cp == NULL) || (pos <= 0)){
printf("单链表为空或pos值不正确，退出运行！");
exit(1);
}
/*从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点*/
while(cp != NULL){
i++;
if(i == pos){
break;
}
ap = cp;
cp = cp->next;
}
/*单链表中没有第pos个结点*/
if(cp == NULL){
printf("pos值不正确，退出运行！");
exit(1);
}
/*若pos等于1，则需要删除表头结点*/
if(pos == 1){
*hl = (*hl)->next; /*或改为*hl = cp->next; */
}
/*否则删除非表头结点，此时cp指向该结点，ap指向前驱结点*/
else{
ap->next = cp->next;
}
/*暂存第pos个结点的值，以便返回*/
temp = cp->data;
free(cp); /*回收被删除的第pos个结点*/
return temp; /*返回在temp中暂存的第pos个结点的值*/
}
/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
int deleteValueList(struct sNode* *hl, elemType x)
{
/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
struct sNode *cp = *hl;
struct sNode *ap = NULL;
/*从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点*/
while(cp != NULL){
if(cp->data == x){
break;
}
ap = cp;
cp = cp->next;
}
/*若查找失败，即该单链表中不存在值为x的结点，则返回0 */
if(cp == NULL){
return 0;
}
/*如果删除的是表头或非表头结点则分别进行处理*/
if(ap == NULL){
*hl = (*hl)->next; /*或改为*hl= cp->next */
}else{
ap->next = cp->next;
}
free(cp); /*回收被删除的结点*/
return 1; /*返回1表示删除成功*/
}
/* 17.交换2个元素的位置*/
void Swip(struct sNode *h1,int i,int j)
{
/*
*/
int temp=0;
if(i==j)
return;
temp=getElem(h1,i);
updatePosList(h1, i, getElem(h1,j));
updatePosList(h1, j, temp);
}
/* 18.将线性表进行快速排序*/
void FastSort(struct sNode *h1, int low,int high)
{
/*
*/
if(low<high)
{
int m = (low+high)/2;
int i=low,j=high;
do
{
while(getElem(h1,j)>getElem(h1,m)) j--;
while(getElem(h1,i)<getElem(h1,m)) i++;
if(i<=j)
{
if(m==j)
m=i;
else if(m==i)
m=i;
Swip(h1,i,j);
i++,j--;
}
}while(i<=j);
/*
printf("\n %5d\n",j);
traverseList(h1);
*/
FastSort(h1,low,j);
FastSort(h1,i,high);
}
}
/*/**/
/************************************************************************/
int main(int argc, char* argv[])
{
int a[NN];
int i;
struct sNode *p, *h, *s;
srand(time(NULL));
initList(&p);
for(i = 0; i < NN; i++){
a[i] = rand() & MM;
}
printf("随机数序列：\n");
for(i = 0; i < NN; i++){
printf("%5d", a[i]);
}
printf(" ");
printf("\n随机数逆序：\n");
for(i = 0; i < NN; i++){
insertFirstList(&p, a[i]);
}
printf("\n随机数产生的序列\n");
traverseList(p);
/*
*/
printf("\n经过快速排序后的序列\n");
FastSort(p,1,sizeList(p));
traverseList(p);
printf("\n单链表长度：%5d ", sizeList(p));
for(h = p; h != NULL; h = h->next){
while(deleteValueList(&(h->next), h->data))
;
}
printf("\n去除重复数：\n");
traverseList(p);
printf("\n单链表长度：%5d ", sizeList(p));
h = NULL;
for(s = p; s != NULL; s = s->next){
insertOrderList(&h, s->data);
}
printf("\n有序表序列：\n");
traverseList(h);
clearList(&p);
system("pause");
return 0;
}

复制代码

		自动登录	找回密码
密码			立即注册