C语言中怎么实现链表,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
C语言 数据结构链表的实例(十九种操作)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*************************************************************************************/
/* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/3091506.html */
/* 第二版博主 原文地址 http://www.cnblogs.com/wireless-dragon/p/5170565.html */
/* 2.创建线性表,此函数输入不为正时终止读取数据*/
/* 3.打印链表,链表的遍历 */
/* 4.查询链表结点数并返回长度 */
/* 5.检查单链表是否为空 */
/* 6.将线性表进行冒泡排序 */
/* 7.查找单链表中第n个结点中的元素 */
/* 8.从单链表中查找具有给定值number的第一个元素,返回该结点的地址 */
/* 9.把单链表中第n个结点的值修改为number的值 */
/* 10.向单链表的表头插入一个元素 */
/* 11.向单链表的末尾添加一个元素 */
/* 12.向单链表中第n个结点位置插入元素为x的结点 */
/* 13.向有序单链表中插入元素x结点,使得插入后仍然有序 */
/* 14.从单链表中删除表头结点 */
/* 15.从单链表中删除表尾结点 */
/* 16.从单链表中删除第n个结点 */
/* 17.从单链表中删除值为x的第一个结点 */
/* 18.交换2个元素的位置 */
/* 19.删除列表 */
/*************************************************************************************/
typedef int elemType;
typedef struct NODE
{
elemType element;
struct NODE *next;
} Node;
/* 2.创建线性表,此函数输入不为正时终止读取数据*/
void creatList(Node **pHead)
{
printf("Please enter the list:\n");
Node *p1, *p2;
p1 = p2 = (Node *)malloc(sizeof(Node));
if (p1 == NULL || p2 == NULL)
exit(0);
memset(p1, 0, sizeof(Node));
scanf("%d", &p1->element);
p1->next = NULL;
while(p1->element > 0)
{
if (*pHead == NULL)
(*pHead) = p1;
else
p2->next = p1;
p2 = p1;
p1 = (Node *)malloc(sizeof(Node));
if (p1 == NULL)
exit(0);
memset(p1, 0, sizeof(Node));
scanf("%d", &p1->element);
p1->next = NULL;
}
}
/* 3.打印链表,链表的遍历 */
void printList(Node *pHead)
{
if (NULL == pHead)
printf("The list is empty\n");
else
while(NULL != pHead)
{
printf("%d ", pHead->element);
pHead = pHead->next;
}
printf("\n");
}
/* 4.查询链表结点数并返回长度 */
int sizeList(Node *pHead)
{
int size = 0;
while(pHead != NULL)
{
size ++;
pHead = pHead->next;
}
return size;
}
/* 5. 检查单链表是否为空 */
void isEmptyList(Node *pHead)
{
if (pHead == NULL)
{
printf("The list is empty\n");
exit(0);
}
}
/* 7.查找单链表中第n个结点中的元素 */
void getElement(Node *pHead, int num)
{
for (int i = 1; i < num; ++i)
pHead = pHead->next;
printf("The value of the %dth element is:%d\n", num, pHead->element);
}
/* 8.从单链表中查找具有给定值number的第一个元素,返回该结点的地址 */
int getElemAddr(Node *pHead, int number)
{
int i = 1;
while(pHead != NULL)
{
if (pHead->element == number)
return i;
i++;
pHead = pHead->next;
}
return 0;
}
/* 9.把单链表中第n个结点的值修改为number的值 */
void modifyElem(Node **pList, int addr, int number)
{
Node *pHead; //在此处如果直接更改pList指向的话,主函数中调用printList就会从addr处开始打印
int i = 1;
pHead = *pList;
while(pHead != NULL)
{
if (i == addr)
break;
pHead = pHead->next;
i++;
}
pHead->element = number;
}
/* 10.向单链表的表头插入一个元素 */
void insertHeadList(Node **pHead)
{
Node *p1;
p1 = (Node *)malloc(sizeof(Node));
if (p1 == NULL)
exit(0);
memset(p1, 0, sizeof(Node));
printf("Please enter a number to be inserted:");
scanf("%d", &p1->element);
p1->next = (*pHead);// 此时pHead指向的是第一个结点(有数据域的),所以新的结点要插入到头结点前
(*pHead) = p1; // pHead指向第一个结点
}
/* 11.向单链表的末尾添加一个元素 */
void insertLastList(Node **pHead, int n)
{
Node *p1, *p2;
p2 = (*pHead);
int i;
for (i = 1; i < n; ++i)
p2 = p2->next;
p1 = (Node *)malloc(sizeof(Node));
if (p1 == NULL)
exit(0);
memset(p1, 0, sizeof(Node));
printf("Please enter a number to be inserted:");
scanf("%d", &p1->element);
p1->next = NULL;
p2->next = p1;
}
/* 12.向单链表中第n个结点位置插入元素为x的结点 */
void isAddPos(Node **pHead, int length)
{
Node *p1, *p2;
int position, i;
printf("Please enter the insert position:");
scanf("%d", &position);
if (position > length || position <= 0)
{
printf("Input error, the program ends\n");
exit(0);
}
p1 = (Node *)malloc(sizeof(Node));
p2 = (*pHead);
if (p1 == NULL)
exit(0);
memset(p1, 0, sizeof(Node));
printf("Please enter a number to be inserted:");
scanf("%d", &p1->element);
for (i = 1; i < position - 1; ++i)
p2 = p2->next;
p1->next = p2->next;
p2->next = p1;
}
/* 6.将线性表进行冒泡排序 */
void Arrange(Node **pHead, int length)
{
Node *p1;
p1 = (*pHead);
int i, j, temp;
for (i = length; i > 0; --i)
{
for(j = i - 1; j > 0; --j)
{
if ((p1->element) > (p1->next->element))
{
temp = p1->element;
p1->element = p1->next->element;
p1->next->element = temp;
}
p1 = p1->next;
}
p1 = (*pHead);
}
}
int OrrderList(Node **pHead, int length)
{
Node *p1, *p2;
p1 = (*pHead);
p2 = (Node *)malloc(sizeof(Node));
if (p2 == NULL)
exit(0);
memset(p2, 0, sizeof(Node));
printf("Enter the value of the element to be inserted:");
scanf("%d", &p2->element);
if (p2->element < p1->element)
{
p2->next = p1;
(*pHead) = p2;
return 1;
}
while(p1->next != NULL && p2->element > (p1->next->element))
p1 = p1->next;
if (p1->next == NULL)
{
p2->next = NULL;
p1->next = p2;
return 1;
}
else
{
p2->next = p1->next;
p1->next = p2;
return 1;
}
}
/* 14.从单链表中删除表头结点 */
void DelHeadList(Node **pHead)
{
Node *p1;
p1 = (*pHead);
(*pHead) = (*pHead)->next;
free(p1);
}
/* 15.从单链表中删除表尾结点 */
void DelLastList(Node **pHead)
{
Node *p1, *p2;
p1 = (*pHead);
p2 = p1->next;
while(p2->next != NULL)
{
p2 = p2->next;
p1 = p1->next;
}
p1->next = NULL;
free(p2);
}
/* 16.从单链表中删除第n个结点 */
void DelPos(Node **pHead, int length)
{
int n, i;
Node *p1, *p2;
p1 = (*pHead);
p2 = p1->next;
printf("Please enter the serial number number to delete:");
scanf("%d", &n);
if (n < 1 || n > length)
exit(0);
for (i = 1; i < n - 1; ++i)
{
p2 = p2->next;
p1 = p1->next;
}
p1->next = p2->next;
free(p2);
}
/* 17.从单链表中删除值为x的第一个结点 */
int Delx(Node **pHead)
{
Node *p1, *p2;
p1 = (*pHead);
p2 = p1->next;
int number;
printf("Please input is going to be deleted the value of x:");
scanf("%d", &number);
if (number == (*pHead)->element)
{
(*pHead) = (*pHead)->next;
free(p1);
return 1;
}
while(p2 != NULL)
{
if (p2->element == number)
{
break;
}
p2 = p2->next;
p1 = p1->next;
}
if (p2 == NULL)
{
printf("X does not exist in the list\n");
return 1;
}
else
{
p1->next = p2->next;
free(p2);
return 1;
}
}
/* 18.交换2个元素的位置 */
void exchange2pos(Node **pHead, int length)
{
Node *p1, *p2;
int n1, n2, i, j, temp;
printf("Please enter the first number:");
scanf("%d", &n1);
printf("Please enter the second number:");
scanf("%d", &n2);
if (n1 < 1 || n1 > length || n2 < 1 || n2 > length)
exit(0);
p1 = p2 = (*pHead);
for (i = 1; i < n1; ++i)
{
p1 = p1->next;
}
for (j = 1; j < n2; ++j)
{
p2 = p2->next;
}
temp = p1->element;
p1->element = p2->element;
p2->element = temp;
}
/* 删除列表 */
void clearList(Node **pHead)
{
Node *p1;
p1 = (*pHead);
while(p1 != NULL)
{
p1 = p1->next;
free((*pHead));
(*pHead) = p1;
}
}
int main(int argc, char const *argv[])
{
/* 1.初始化线性表,即置单链表的表头指针为空 */
Node *pList = NULL;
int length = 0, n, addr, number;
/* 2.创建线性表,此函数输入不为正时终止读取数据*/
printf("- - - - - - - - - 2 - - - - - - - -\n");
creatList(&pList);
/* 5. 检查单链表是否为空 */
isEmptyList(pList);
printList(pList);
/* 4.查询链表结点数并返回长度 */
printf("- - - - - - - - - 4 - - - - - - - -\n");
length = sizeList(pList);
printf("the Node length is:%d\n", length);
/* 7.查找单链表中第n个结点中的元素 */
printf("- - - - - - - - - 7 - - - - - - - -\n");
printf("Please input node number (n):");
scanf("%d", &n);
if (n > length || n < 1)
{
printf("N is not within the scope of\n");
exit(0);
}
getElement(pList, n);
/* 8.从单链表中查找具有给定值number的第一个元素,返回该结点的地址 */
printf("- - - - - - - - - 8 - - - - - - - -\n");
addr = 0;
number;
printf("Please enter to find element value (number):");
scanf("%d", &number);
addr = getElemAddr(pList, number);
if (addr == 0)
printf("List the element\n");
else
printf("The location of the number is:%d\n", addr);
/* 9.把单链表中第n个结点的值修改为number的值 */
printf("- - - - - - - - - 9 - - - - - - - -\n");
addr = 0;
number = 0;
printf("Please input to replace the serial number (n):");
scanf("%d", &addr);
if (addr > length || addr < 0)
{
printf("N is not within the scope of\n");
exit(0);
}
printf("Please input to replace the contents of the (number):");
scanf("%d", &number);
modifyElem(&pList, addr, number);
printf("The revised list is:\n");
printList(pList);
/* 10.向单链表的表头插入一个元素 */
printf("- - - - - - - - - 10 - - - - - - - -\n");
insertHeadList(&pList);
printList(pList);
/* 11.向单链表的末尾添加一个元素 */
printf("- - - - - - - - - 11 - - - - - - - -\n");
insertLastList(&pList, length);
printList(pList);
/* 12.向单链表中第n个结点位置插入元素值为x的结点 */
printf("- - - - - - - - - 12 - - - - - - - -\n");
isAddPos(&pList, length);
printList(pList);
/* 6.将线性表进行冒泡排序 */
printf("- - - - - - - - - 6 - - - - - - - -\n");
Arrange(&pList, length);
printList(pList);
/* 13.向有序单链表中插入元素x结点,使得插入后仍然有序 */
printf("- - - - - - - - - 13 - - - - - - - -\n");
OrrderList(&pList, length);
printList(pList);
/* 14.从单链表中删除表头结点 */
printf("- - - - - - - - - 14 - - - - - - - -\n");
DelHeadList(&pList);
printList(pList);
/* 15.从单链表中删除表尾结点 */
printf("- - - - - - - - - 15 - - - - - - - -\n");
DelLastList(&pList);
printList(pList);
/* 16.从单链表中删除第n个结点 */
printf("- - - - - - - - - 16 - - - - - - - -\n");
DelPos(&pList, length);
printList(pList);
/* 17.从单链表中删除值为x的第一个结点 */
printf("- - - - - - - - - 17 - - - - - - - -\n");
Delx(&pList);
printList(pList);
/* 18.交换2个元素的位置 */
printf("- - - - - - - - - 18 - - - - - - - -\n");
exchange2pos(&pList, length);
printList(pList);
/* 19.删除列表 */
printf("- - - - - - - - - 19 - - - - - - - -\n");
clearList(&pList);
printList(pList);
return 0;
}
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。