用C语言编写一个完整的实现单链表(带头结点)的基本操作(包括查找、插 ...
发布网友
发布时间：1小时前
共2个回答
热心网友
时间：1小时前
# include <stdio.h>
# include <stdlib.h>
typedef struct Node
{
int data;
struct Node * pNext;
} NODE, *PNODE;
PNODE creat_list(void);//创建链表
void travser_list(PNODE pHead);//遍历链表
void add_list(PNODE pHead, int val);//追加链表
bool empty_list(PNODE pHead);//判断链表是否为空
bool insert_list(PNODE pHead, int pos, int val);//插入链表节点
bool delete_list(PNODE pHead, int pos, int *pVal);//删除链表节点
int length_list(PNODE pHead);//求链表长度
bool find_list(PNODE pHead, int pos, int *pVal);//查找链表
void inversion_list(PNODE pHead);//倒置链表
void sort_list(PNODE pHead);//排序链表
void clear_list(PNODE pHead);//清空链表
int main (void)
{
int val;
int len;
PNODE pHead = NULL;
pHead = creat_list();
travser_list(pHead);
add_list(pHead, 78);
add_list(pHead, 45);
add_list(pHead, 0);
add_list(pHead, 17);
travser_list(pHead);
insert_list(pHead, 3, -12);
travser_list(pHead);
if (delete_list(pHead, 4, &val))
{
printf("删除节点成功！删除的值为：%d\n", val);
}
else
printf("删除失败!");
travser_list(pHead);
len = length_list(pHead);
printf("链表的长度为：%d\n", len);
if (find_list(pHead, 10, &val))
{
printf("查找成功！查找的值为：%d\n", val);
}
else
{
printf("查找失败!查找节点不存在!\n");
}
inversion_list(pHead);
travser_list(pHead);
sort_list(pHead);
travser_list(pHead);
printf("下面是清除后的链表!");
clear_list(pHead);
travser_list(pHead);
return 0;
}
PNODE creat_list(void)
{
PNODE pHead;
int num;
int i;
int val;
pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("动态内存分配失败!");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext = NULL;
printf("请输入链表节点的个数：");
scanf("%d", &num);
for (i = 0; i < num; ++i)
{
PNODE pNew;
pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("动态内存分配失败!");
exit(-1);
}
printf("请给第%d个节点赋值：", i+1);
scanf("%d", &val);
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
void travser_list(PNODE pHead)
{
PNODE p = pHead;
while (NULL != p->pNext)
{
p = p->pNext;
printf("%4d", p->data);
}
printf("\n");
return;
}
void add_list(PNODE pHead, int val)
{
PNODE p = pHead;
while (NULL != p->pNext)
{
p = p->pNext;
}
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("动态内存分配失败!");
exit(-1);
}
pNew->data = val;
p->pNext = pNew;
pNew->pNext = NULL;
p = pNew;
}
bool empty_list(PNODE pHead)
{
if (NULL == pHead->pNext)
return true;
return false;
}
bool insert_list(PNODE pHead, int pos, int val)
{
PNODE p = pHead;
int i = 0;
while(NULL != p && i < pos -1)
{
p = p->pNext;
i++;
}
if (NULL == p || i > pos-1)
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("动态内存分配失败!");
exit(-1);
}
pNew->data = val;
pNew->pNext = p->pNext;
p->pNext = pNew;
return true;
}
bool delete_list(PNODE pHead, int pos, int *pVal)
{
PNODE p = pHead;
int i = 0;
while (NULL != p->pNext && i < pos-1)
{
p = p->pNext;
i++;
}
if (NULL == p->pNext || i > pos-1)
return false;
PNODE r = p->pNext;
*pVal = r->data;
p->pNext = r->pNext;
free(r);
r = NULL;
return true;
}
int length_list(PNODE pHead)
{
int length = 0;
PNODE p = pHead;
while (NULL != p->pNext)
{
p = p->pNext;
length++;
}
printf("\n");
return length;
}
bool find_list(PNODE pHead, int pos, int *pVal)
{
PNODE p = pHead;
int i = 0;
while (NULL != p->pNext && i < pos-1)
{
p = p->pNext;
++i;
}
if (NULL == p->pNext || i > pos-1)
return false;
*pVal = p->pNext->data;
return true;
}
void inversion_list(PNODE pHead)
{
int len;
len = length_list(pHead);
int i, j, t;
PNODE p = pHead;
PNODE q ;
for (i = 0; i < len; ++i)
{
p = p->pNext;
q = p;
for (j = i; j < len - i-1; ++j)
{
q = q->pNext;
}
t = p->data;
p->data = q->data;
q->data = t;
}
printf("\n");
return;
}
void sort_list(PNODE pHead)
{
int len;
len = length_list(pHead);
int i, j, t;
PNODE p = pHead;
PNODE q;
for (i = 0; i < len; ++i)
{
p = p->pNext;
q = p;
for (j = i; j < len-1; ++j)
{
q = q->pNext;
if (p->data > q->data)
{
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
printf("\n");
return;
}
void clear_list(PNODE pHead)
{
PNODE p = pHead;
PNODE r ;
int i;
int len = length_list(pHead);
for (i = 0; i < len; ++i)
{
r = p;
r = r->pNext;
p->pNext = r->pNext;
free(r);
}
r = NULL;
return;
}
热心网友
时间：1小时前
typedef struct node
{
char name[20];
struct node *link;
}stud;
这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继的指针。
定义好了链表的结构之后，只要在程序运行的时候爱数据域中存储适当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为null。
下面就来看一个建立带表头（若未说明，以下所指链表均带表头）的单链表的完整程序。
#include ＜stdio.h＞
#include ＜malloc.h＞ /*包含动态内存分配函数的头文件*/
#define n 10 /*n为人数*/
typedef struct node
{
char name[20];
struct node *link;
}stud;
stud * creat(int n) /*建立单链表的函数，形参n为人数*/
{
stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/
int i; /*计数器*/
if((h=(stud *)malloc(sizeof(stud)))==null) /*分配空间并检测*/
{
printf(\"不能分配内存空间!\");
exit(0);
}
h-＞name[0]=\'\\0\'; /*把表头结点的数据域置空*/
h-＞link=null; /*把表头结点的链域置空*/
p=h; /*p指向表头结点*/
for(i=0;i＜n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==null) /*分配新存储空间并检测*/
{
printf(\"不能分配内存空间!\");
exit(0);
}
p-＞link=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/
printf(\"请输入第%d个人的姓名\",i+1);
scanf(\"%s\",s-＞name); /*在当前结点s的数据域中存储姓名*/
s-＞link=null;
p=s;
}
return(h);
}
main()
{
int number; /*保存人数的变量*/
stud *head; /*head是保存单链表的表头结点地址的指针*/
number=n;
head=creat(number); /*把所新建的单链表表头地址赋给head*/
}
这样就写好了一个可以建立包含n个人姓名的单链表了。写动态内存分配的程序应注意，请尽量对分配是否成功进行检测。
