C语言数据结构实现链表逆序并输出

2024-02-25 21:05:03 146

C语言数据结构实现链表逆序并输出

将一个链表逆序并输出。我用了两种方法来实现，第一种是借助了一个新的空链表；第二种是在原来链表的基础上直接实现逆序。

实例代码：

头文件：

#include
#include
#include

typedefintElemType;
typedefstructNode
{//结点结构
ElemTypevalue;//值域
structNode*next;//指针域
}Node,*ptr_Node;

typedefstructLinkList
{//链表结构
ptr_Nodehead;//链表头结点指针
ptr_Nodetail;//链表尾结点指针
intlength;//链表长度
}LinkList,*ptr_LinkList;

ptr_LinkListCreateList(void)
{//创建一个空链表
ptr_LinkListlinklist;
linklist=(LinkList*)malloc(sizeof(LinkList));
if(!linklist)
{
printf("allocationfailed.\n");
}
linklist->head=NULL;
linklist->tail=NULL;
linklist->length=0;
returnlinklist;
}

boolIsListEmpty(ptr_LinkListlinklist)
{//判断链表是否为空
if(linklist->length==0)
{
returntrue;
}
returnfalse;
}

voidInsertListHead(ptr_LinkListlinklist,ElemTypeelement)
{//在表头插入值为element的结点作为新的表头
ptr_Nodeptr_node;
ptr_node=(Node*)malloc(sizeof(Node));//生成插入结点
if(!ptr_node)
{
printf("allocationfailed.\n");
}
else
{
ptr_node->value=element;
if(linklist->length==0)
{
linklist->head=ptr_node;
linklist->tail=linklist->head;
linklist->tail->next=NULL;
}
else
{
ptr_node->next=linklist->head;
linklist->head=ptr_node;//链表头
}
linklist->length++;//链表长度加1
}
}

voidInsertListTail(ptr_LinkListlinklist,ElemTypeelement)
{
ptr_Nodeptr_node;
ptr_node=(Node*)malloc(sizeof(Node));//生成插入结点
if(!ptr_node)
{
printf("allocationfailed.\n");
}
else
{
ptr_node->value=element;
if(linklist->length==0)
{
linklist->head=ptr_node;
linklist->tail=linklist->head;
linklist->tail->next=NULL;
}
else
{
linklist->tail->next=ptr_node;
linklist->tail=ptr_node;//链表尾
}
linklist->length++;//链表长度加1
}
}

voidInsertListPosition(ptr_LinkListlinklist,intpos,ElemTypeelement)
{
inti;
ptr_Nodeptr_node;
ptr_Nodetemp_ptr_node;
if(pos<1||pos>linklist->length)
{
printf("Theinsertpositionisinvalidate.\n");
}
else
{
ptr_node=(Node*)malloc(sizeof(Node));//生成插入结点
if(!ptr_node)
{
printf("allocationfailed.\n");
}
ptr_node->value=element;
if(pos==1)
{
InsertListHead(linklist,element);
}
elseif(pos==linklist->length)
{
InsertListTail(linklist,element);
}
else
{
temp_ptr_node=linklist->head;
for(i=1;inext;
}
ptr_node->next=temp_ptr_node->next;
temp_ptr_node->next=ptr_node;
linklist->length++;
}
}
}

voidDestroy(ptr_LinkListlinklist)
{//销毁链表
ptr_Nodep=linklist->head;
ptr_Nodeq;
while(p)
{//释放每个结点空间
q=p->next;
free(p);
p=NULL;
p=q;
}
}

voidTraverse(ptr_LinkListlinklist)
{//输出整个链表
ptr_Nodep;
p=linklist->head;
while(p)
{
printf("%4d",p->value);
p=p->next;
}
}

头文件中实现了链表的几个基本的操作，有的是必须的，有些是非必须的。

实现代码：

#include"stdafx.h"
#include"LinkList.h"
#include

ptr_LinkListInvertList(ptr_LinkListlist)
{//该方法借助一个新的空链表来实现链表逆序
ptr_LinkListinverted_linklist;
ptr_Nodep;
p=list->head;
inverted_linklist=CreateList();//创建一个空链表
while(p)
{//将list链表中的结点值逆序输入新创建的链表中，实现链表反转
InsertListHead(inverted_linklist,p->value);
p=p->next;
}
returninverted_linklist;
}

voidInvertLinkList(ptr_LinkListlinklist)
{//该方法直接对原有链表实现逆序，不借助其他链表
ptr_Nodep,q,r,m;
m=p=linklist->head;
q=p->next;
r=q->next;
while(r)
{//依次对链表中的结点进行反转
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;//最后一个结点反转
linklist->head=q;
linklist->tail=m;
linklist->tail->next=NULL;
}

int_tmain(intargc,_TCHAR*argv[])
{
ptr_LinkListlinklist;
ptr_LinkListlist;
linklist=CreateList();
if(linklist)
{
printf("Wehavecreatedanewlinklist.\n");
}
InsertListHead(linklist,12);
InsertListHead(linklist,35);
InsertListHead(linklist,66);
InsertListHead(linklist,06);
InsertListHead(linklist,11);
InsertListHead(linklist,54);
InsertListHead(linklist,79);
Traverse(linklist);
printf("\n");
printf("Thefirstmethod:\n");
list=InvertList(linklist);
Traverse(list);
printf("\n");
printf("Thesecondmethod:\n");
InvertLinkList(linklist);
Traverse(linklist);
printf("\n");
getch();
return0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

C语言数据结构实现链表逆序并输出

热门推荐

随机推荐