您的位置:

c语言双相链表,C语言双向链表

本文目录一览:

C语言、双向链表

//Node.h 声明类Node

#ifndef Node_H

#define Node_H

template class T

class LinkList; //为是Node类的友员类而声明

template class T

class Node

{

public:

friend class LinkListT; //将LinkList类设为友元类

private:

T data;

NodeT *next;

};

#endif

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。//LinkList.h 声明类LinkList

#ifndef LinkQueue_H

#define LinkQueue_H

#include "Node.h"

template class T

class LinkList

{

public:

LinkList( ); //建立只有头结点的空链表

LinkList(T a[], int n); //建立有n个元素的单链表

~LinkList( ); //析构函数

int Length( ); //求单链表的长度

T Get(int i); //取单链表中第i个结点的元素值

int Locate(T x); //求单链表中值为x的元素序号

void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点

T Delete(int i); //在单链表中删除第i个结点

void PrintList( ); //遍历单链表,按序号依次输出各元素

private:

NodeT *first; //单链表的头指针

};

#endif

。。。。。。。。。。。。。。。。。。。

//LinkList.cpp

#include "LinkList.h"

/*

*前置条件:单链表不存在

*输 入:无

*功 能:构建一个单链表

*输 出:无

*后置条件:构建一个单链表

*/

template class T

LinkListT:: LinkList( )

{

first=new NodeT; first-next=NULL;

}

/*

*前置条件:单链表不存在

*输 入:顺序表信息的数组形式a[],单链表长度n

*功 能:将数组a[]中元素建为长度为n的单链表

*输 出:无

*后置条件:构建一个单链表

*/

template class T

LinkListT:: LinkList(T a[ ], int n)

{

first=new NodeT; //生成头结点

NodeT *r,*s;

r=first; //尾指针初始化

for (int i=0; in; i++)

{

s=new NodeT; s-data=a[i]; //为每个数组元素建立一个结点

r-next=s; r=s; //插入到终端结点之后

}

r-next=NULL; //单链表建立完毕,将终端结点的指针域置空

}

/*

*前置条件:无

*输 入:无

*功 能:无

*输 出:无

*后置条件:无

*/

template class T

LinkListT:: ~LinkList()

{

}

/*

*前置条件:单链表存在

*输 入:查询元素位置i

*功 能:按位查找位置为i的元素并输出值

*输 出:查询元素的值

*后置条件:单链表不变

*/

template class T

T LinkListT::Get(int i)

{

NodeT *p; int j;

p=first-next; j=1; //或p=first; j=0;

while (p ji)

{

p=p-next; //工作指针p后移

j++;

}

if (!p) throw "位置";

else return p-data;

}

/*

*前置条件:单链表存在

*输 入:查询元素值x

*功 能:按值查找值的元素并输出位置

*输 出:查询元素的位置

*后置条件:单链表不变

*/

template class T

int LinkListT::Locate(T x)

{

NodeT *p; int j;

p=first-next; j=1;

if(pp-next){

while(p-data!=x)

{

p=p-next;

j++;

}

return j;

}

else throw "位置";

}

/*

*前置条件:单链表存在

*输 入:插入元素x,插入位置i

*功 能:将元素x插入到单链表中位置i处

*输 出:无

*后置条件:单链表插入新元素

*/

template class T

void LinkListT::Insert(int i, T x)

{

NodeT *p; int j;

p=first ; j=0; //工作指针p初始化

while (p ji-1)

{

p=p-next; //工作指针p后移

j++;

}

if (!p) throw "位置";

else {

NodeT *s;

s=new NodeT;

s-data=x; //向内存申请一个结点s,其数据域为x

s-next=p-next; //将结点s插入到结点p之后

p-next=s;

}

}

/*

*前置条件:单链表存在

*输 入:无

*功 能:输出单链表长度

*输 出:单链表长度

*后置条件:单链表不变

*/

template class T

int LinkListT::Length( )

{

Node T *p = first-next;

int i = 0;

while(p)

{

p = p-next;

i++;

}

return i;

}

/*

*前置条件:单链表存在

*输 入:要删除元素位置i

*功 能:删除单链表中位置为i的元素

*输 出:无

*后置条件:单链表删除元素

*/

template class T

T LinkListT::Delete(int i)

{

NodeT *p; int j;

p=first ; j=0; //工作指针p初始化

while (p ji-1) //查找第i-1个结点

{

p=p-next;

j++;

}

if (!p || !p-next) throw "位置"; //结点p不存在或结点p的后继结点不存在

else {

NodeT *q; int x;

q=p-next; x=q-data; //暂存被删结点

p-next=q-next; //摘链

delete q;

return x;

}

}

/*

*前置条件:单链表存在

*输 入:无

*功 能:单链表遍历

*输 出:输出所有元素

*后置条件:单链表不变

*/

template class T

void LinkListT::PrintList( )

{

NodeT *p;

p=first-next;

while (p)

{

coutp-dataendl;

p=p-next;

}

}

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。#includeiostream.h

#include"LinkList.cpp"

#include"Node.h"

void main( )

{

LinkList int a;

cout"执行插入操作:"endl;

try

{

a.Insert(1,4);

a.Insert(2,5);

a.Insert(3,6);

}

catch(char* wrong)

{

cout wrong; //如失败提示失败信息

}

cout"已经插入“4,5,6”"endl;

cout"单链表a的长度为:"endl;

couta.Length()endl; //返回单链表长度

coutendl;

cout"单链表a的元素为:"endl;

a.PrintList(); //显示链表中所有元素

coutendl;

cout"按位查找第二个元素:"endl;

cout"第二个元素为:";

couta.Get(2)endl; //查找链表中第二个元素

coutendl;

cout"按值查找5"endl;

cout"值为5的元素位置为:";

couta.Locate(5)endl; //查找元素5,并返回在单链表中位置

coutendl;

cout"执行删除4的操作"endl;

a.Delete(1); //删除元素4

cout"已删除成功,单链表a的长度为";

couta.Length()endl;

coutendl;

cout"链表a中的元素为:"endl;

a.PrintList();

int r[ ]={1,2,3,4,5};

LinkList int b(r,5); //根据数组创建顺序表

cout"执行插入操作前单链表b为:"endl;

b.PrintList(); //输出单链表所有元素

cout"插入前单链表b的长度为:";

coutb.Length()endl;

try

{

b.Insert(3,8);

}

catch(char* wrong)

{

cout wrong; //如失败提示失败信息

}

cout"执行插入操作后单链表b为:"endl;

b.PrintList(); //输出单链表b所有元素

cout"插入后单链表b的长度为:";

coutb.Length()endl;

coutendl;

try

{

if(a.Length()){

cout"执行删除第一个元素操作:"endl;

coutendl;

b.Delete(1); //删除b中第一个元素

cout"已删除成功,单链表b的长度为:";

coutb.Length()endl;

}

else{

cout"顺序表b长度为0"endl;

}

}

catch(char* wrong)

{

cout wrong; //如失败提示失败信息

}

cout"执行插入操作后单链表b为:"endl;

b.PrintList(); //输出单链表所有元素

}

C语言双向链表

#include "stdio.h"

#include "stdlib.h"

typedef int ElemType;//元素类型

typedef struct DuLNode

{//双向链表

ElemType data;

struct DuLNode *prior, *next;

}DuLNode,*DuLinkList;

int Create(DuLinkList L)

{//建立双向链表

DuLinkList p,q;

ElemType n,i;

L = (DuLinkList) malloc (sizeof(DuLNode));

L-next = NULL;

q = L;

printf("输入数据个数:");

scanf("%d",n);

printf("输入数据元素:");

for ( i = 0; i n; i++)

{

p = (DuLinkList) malloc (sizeof(DuLNode));

scanf("%d",p-data);//插入数据

p-prior = q;

q-next = p;

p-next = 0;

q = q-next;

}

return 1;

}

int Visit(DuLinkList L)

{//遍历双向链表

DuLinkList p;

p = L-next;

printf("双向链表为:");

while (p)

{

printf("%4d",p-data);

p = p-next;

}

printf("\n");

return 1;

}

int Clear(DuLinkList L)

{

DuLinkList p;

p = L-next;

while(p)

{

L-next = p-next;

free(p);

p = L-next;

}

return 1;

}

main()

{

int i,e,s,num;

char c='y';

DuLinkList L;

Create(L);

Visit(L);

while (c=='y')

{

printf("\n\n\n1.双向链表插入元素\n2.双向链表中删除元素\n");

printf("3.判断双向链表元素是否对称\n");

printf("4.双向链表中奇数排在偶数前面\n");

printf("5.建立递增链表并有序插入元素\n\n");

printf("选择需要的操作\n\n");

scanf("%d",num);

switch(num)

{

case 1:

printf("输入插入元素位置以及元素:\n");

scanf("%d%d",i,e);

ListInsert(L, i, e);

Visit(L);

break;

case 2:

printf("输入删除元素位置:");

scanf("%d",i);

Delete(L,i,s);

printf("删除的元素为:%d\n",s);

Visit(L);

break;

case 3:

if(Same(L)) printf("链表对称\n");

else printf("链表不对称\n");

break;

case 5:

printf("清空原链表,建立递增链表:\n");

XCreate(L);

Visit(L);

break;

case 4:

printf("奇数放在偶数前面:\n");

Jiou(L);

Visit(L);

break;

}

printf("继续操作(y/n):\n");

scanf("%s",c);

}

}

C语言定义双向链表结构体

struct

node

{

DataType

data;

node

*

prior;

node

*

next;

};

其中prior指针用来存储前一节点的地址,next用来存储后一节点的地址,就比单项链表多了一个指针而已,可以添加其它自定义的数据成员

使用C语言实现双向链表的建立、删除和插入

#includestdio.h

#includestdlib.h

#includemalloc.h

struct list{

int data;

struct list *next;

struct list *pre;

};

typedef struct list node;

typedef node *link;

link front=NULL,rear,ptr,head=NULL;

link push(int item){

link newnode=(link)malloc(sizeof(node));

newnode-data=item;

if(head==NULL)

{

head=newnode;

head-next=NULL;

head-pre=NULL;

rear=head;

}

else

{

rear-next=newnode;

newnode-pre=rear;

newnode-next=NULL;

rear=newnode;

}

return head;

}

void makenull(){

front=NULL;

rear=NULL;

}

empty(){

if(front==NULL)

return 1;

else

return 0;

}

int tops(){

if(empty())

return NULL;

else

return rear-data;

}

void pop(){

if(empty())

printf("stack is empty!\n");

else

rear=rear-pre;

}

void display(link l){

link p;

p=l;

while(p!=NULL){

printf("%d-",p-data);

p=p-next;

}

}

void main(){

int n,i;

printf("input your first data!\n");

scanf("%d",n);

front=push(n);

/*another data*/

for(i=0;i3;i++)

{

printf("input:\n");

scanf("%d",n);

push(n);

}

ptr=front;

display(ptr);

printf("\n Please enter any key to pop");

pop();

ptr=front;

display(ptr);

}

求问c语言单向链表和双向链表与循环链表的区别

打个比方。把链表节点看作是一个人,把链表指针看作是人的手(左手是前向指针,右手是后向指针)。

非循环的单向链表是这样的:若干个人排成一排,每个人都抬起右手指向他右边的人,最右边的人的右手指向了空气(NULL)。如果要想找到这一排中任意一个人,必须从排头(链表头)开始沿手指的方向挨个查找。

循环单向链表是这样的:若干个人围成一圈,每个人都抬起右手指向他右边的人,这样每个人的右手都能指到一个人(如果只有一个人,那么他的右手指向自己)。从任意一个人开始,沿着手指的方向,可以不停地循环找到每一个人。

非循环的双向链表是这样的:若干个人排成一排,每个人都抬起左手指向他左边的人,并且每个人都抬起右手指向他右边的人,那么最左边的人的左手指向了空气(NULL),最右边的人的右手指向了空气(NULL)。如果要想找到这一排中某个目标人,从任意一个人开始,可以沿左手方向尝试查找,如果找不到,可以继续沿右手方向查找,直到找到目标人。

循环双向链表是这样的:若干个人围成一圈,每个人都抬起左手指向他左边的人,并且每个人都抬起右手指向他右边的人,这样每个人的左右手都可以指到一个人(如果只有一个人,那么他的左右手都指向自己)。无论选择左手方向还是右手方向,都可以不停地循环找到每一个人。