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;
}
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!