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

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

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

实例代码:

    头文件:  

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

typedef int ElemType;

typedef struct Node

{//结点结构

ElemType value; //值域

struct Node *next;//指针域

}Node,*ptr_Node;

typedef struct LinkList

{//链表结构

ptr_Node head; //链表头结点指针

ptr_Node tail;//链表尾结点指针

int length; //链表长度

}LinkList,*ptr_LinkList;

ptr_LinkList CreateList(void)

{//创建一个空链表

ptr_LinkList linklist;

linklist=(LinkList *)malloc(sizeof(LinkList));

if(!linklist)

{

printf("allocation failed.\n");

}

linklist->head=NULL;

linklist->tail=NULL;

linklist->length=0;

return linklist;

}

bool IsListEmpty(ptr_LinkList linklist)

{//判断链表是否为空

if(linklist->length==0)

{

return true;

}

return false;

}

void InsertListHead(ptr_LinkList linklist,ElemType element)

{//在表头插入值为element的结点作为新的表头

ptr_Node ptr_node;

ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点

if(!ptr_node)

{

printf("allocation failed.\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

}

}

void InsertListTail(ptr_LinkList linklist,ElemType element)

{

ptr_Node ptr_node;

ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点

if(!ptr_node)

{

printf("allocation failed.\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

}

}

void InsertListPosition(ptr_LinkList linklist,int pos,ElemType element)

{

int i;

ptr_Node ptr_node;

ptr_Node temp_ptr_node;

if(pos<1 || pos>linklist->length)

{

printf("The insert position is invalidate.\n");

}

else

{

ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点

if(!ptr_node)

{

printf("allocation failed.\n");

}

ptr_node->value=element;

if(pos==1)

{

InsertListHead(linklist,element);

}

else if(pos==linklist->length)

{

InsertListTail(linklist,element);

}

else

{

temp_ptr_node=linklist->head;

for(i=1;i<pos-1;i++)

{//找到第pos-1个结点

temp_ptr_node=temp_ptr_node->next;

}

ptr_node->next=temp_ptr_node->next;

temp_ptr_node->next=ptr_node;

linklist->length++;

}

}

}

void Destroy(ptr_LinkList linklist)

{//销毁链表

ptr_Node p=linklist->head;

ptr_Node q;

while(p)

{//释放每个结点空间

q=p->next;

free(p);

p=NULL;

p=q;

}

}

void Traverse(ptr_LinkList linklist)

{//输出整个链表

ptr_Node p;

p=linklist->head;

while(p)

{

printf("%4d",p->value);

p=p->next;

}

}

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

    实现代码:  

#include "stdafx.h"

#include "LinkList.h"

#include <conio.h>

ptr_LinkList InvertList(ptr_LinkList list)

{//该方法借助一个新的空链表来实现链表逆序

ptr_LinkList inverted_linklist;

ptr_Node p;

p=list->head;

inverted_linklist=CreateList();//创建一个空链表

while(p)

{//将list链表中的结点值逆序输入新创建的链表中,实现链表反转

InsertListHead(inverted_linklist,p->value);

p=p->next;

}

return inverted_linklist;

}

void InvertLinkList(ptr_LinkList linklist)

{//该方法直接对原有链表实现逆序,不借助其他链表

ptr_Node p,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(int argc, _TCHAR* argv[])

{

ptr_LinkList linklist;

ptr_LinkList list;

linklist=CreateList();

if(linklist)

{

printf("We have created a new linklist.\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("The first method:\n");

list=InvertList(linklist);

Traverse(list);

printf("\n");

printf("The second method:\n");

InvertLinkList(linklist);

Traverse(linklist);

printf("\n");

getch();

return 0;

}

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

以上是 C语言数据结构实现链表逆序并输出 的全部内容, 来源链接: utcz.com/z/342622.html

回到顶部