Question

编写一个C语言程序 实现单链表的基本操作

要求实现单链表的基本操作，包括链表的建立、释放、查找、插入、删除等函数，要求同时具备输入输出功能。

Answer 1

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node
{
int data;
struct Node * pNext;
} * PNODE, NODE;

PNODE establish_list (void);
void traverse_list (PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
void sort_list(PNODE pHead);
void insert_list(PNODE pHead, int pos, int val);
int delete_list(PNODE pHead, int pos, int val);
void freeer(PNODE pHead);

int main(void)
{
PNODE pHead;
int len, i, j, val;
pHead = establish_list();
traverse_list(pHead);

if(is_empty(pHead))
printf("链表为空\n");
else
printf("链表不空\n");

len = length_list(pHead);
printf("链表的长度为: %d\n", len);

sort_list(pHead);
traverse_list(pHead);

printf("请输入您要在第几个节点插入\n");
scanf("%d", &i);
printf("请输入您要在第%d个节点插入的值\n", i);
scanf("%d", &j);
insert_list(pHead, i, j);
traverse_list(pHead);
printf("请输入您要第几个删除的节点\n");
scanf("%d", &i);
val = delete_list(pHead, i, val);
printf("您删除的节点值为: %d\n", val);
traverse_list(pHead);
freeer(pHead);

return 0;
}

PNODE establish_list(void)//初始化链表，返回头结点地址
{
int val, len;
PNODE Tem;
PNODE pNew;
PNODE pHead;

pHead = (PNODE)malloc(sizeof(NODE));
Tem = pHead;
if(NULL == pHead)
{
printf("分配失败");
exit(-1);
}
Tem->pNext = NULL;
printf("请输入您要定义节点的长度: ");
scanf("%d", &len);

for (int i=0;i<len;++i)
{
printf("请输入第%d个节点的值: ", i+1);
scanf("%d", &val);

pNew = (PNODE)malloc(sizeof(NODE));

if(NULL == pNew)
{
printf("分配失败");
exit(-1);
}
pNew->data = val;//首先把本次创建的新节点的值付给新节点的数据域
Tem->pNext = pNew;//然后使用临时的节点变量的指针域保存了新节点的地址，也就是指向了新节点
pNew->pNext = NULL;//如何再不循环，新节点成为最后一个节点
Tem = pNew;//把本次分配的新节点完全的赋给Tem，Tem就成为了这次新节点的影子,那么下次分配新节点时可以使用上个新节点的数据
}
return pHead;
}

void traverse_list(PNODE pHead)
{
PNODE p = pHead;//使用P是为了不改写头结点里保存的地址
p = pHead->pNext;//使P指向首节点

while(p != NULL)//P本来就是头结点的指针域，也就是首节点的地址，既然是地址就可以直接判断p是否等于NULL
{
printf("%d ", p->data);
p = p->pNext;//使P每循环一次就变成P的下一个节点
}
}

bool is_empty(PNODE pHead)
{
if(NULL == pHead->pNext)
return true;
else
return false;
}

int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int len = 0;

while(p != NULL)
{
len++;
p = p->pNext;
}
return len;
}

void sort_list(PNODE pHead)
{
int i, j, t, len;
PNODE p, q;
len = length_list(pHead);

for(i=0,p=pHead->pNext;i<len;i++,p=p->pNext)//逗号后只是为了找到下一个节点，因为不是数组，所以不能使用下标来++
{
for(j=0,q=pHead->pNext;j<len;j++,q=q->pNext)
if(q->data > p->data)//这里的大小与号可以决定是升序还是降序，如果是大于号就是升序,反之小于号就是降序
{
t = q->data;
q->data = p->data;
p->data = t;
}
}

return;
}

void insert_list(PNODE pHead, int pos, int val)
{
int i;
PNODE q = pHead;
PNODE p = pHead;
if(pos > 0 && pos <= length_list(pHead))
{
for(i=0;i<pos;i++)
{
q = q->pNext;//q就是要插入的连接点
}
for(i=1;i<pos;i++)
{
p = p->pNext;//p就是要插入连接点的前一个节点
}
PNODE pNew = (PNODE)malloc(sizeof(NODE));
p->pNext = pNew;
pNew->data = val;
pNew->pNext = q;
}
else if(pos > length_list(pHead))//追加
{
PNODE t;
t = pHead;
PNODE PN;
PN = (PNODE)malloc(sizeof(NODE));
if(PN == NULL)
printf("分配失败");
else
while(t->pNext != NULL)
{
t = t->pNext;//使T->pNext成为尾结点
}
PN->data = val;//给新节点赋予有效数据
t->pNext = PN;//使尾结点的指针域指向了新的结点
PN->pNext = NULL;//新节点成为尾结点
}
else
printf("error\n");
return;
}

int delete_list(PNODE pHead, int pos, int val)
{
int i, j;
PNODE q, p;
q = pHead;
p = pHead;

if(pos > 0 && pos <= length_list(pHead))//保证删除的是节点的有效数
{
for(i=0;i<pos;i++)
{
p = p->pNext;
}
for(j=1;j<pos;j++)
{
if(pos == 0)
q = pHead;
else
q = q->pNext;
}
q->pNext = p->pNext;
val = p->data;

free(p);
return val;
}
else
printf("error");

}

void freeer(PNODE pHead)
{
PNODE pT = pHead;
while(NULL != pHead->pNext)
{
free(pT);
pT = pT->pNext;
}

return;
}
/*
好久以前写的一个链表了，有排序，插入，删除，输出，判断是否为空，甚至还有释放堆中内存的功能
*/

Answer 2

邮箱？有时间给你发