c語言實現雙向鏈表

㈠ c語言數據結構（雙向鏈表排序）

#include<stdio.h>
#include<malloc.h>

#define ElemType int

int count=0;

typedef struct DulNode
{
ElemType data;
DulNode *prior;
DulNode *next;
}DulNode,*DulLinkList;

//初始化鏈表，結束後產生一個頭結點指針
void InitDLList(DulLinkList *L)
{
(*L)=(DulLinkList)malloc(sizeof(DulNode));
(*L)->next=*L;
(*L)->prior=(*L)->next;
}
//對鏈表進行插入操作
void ListInsert(DulLinkList *L)
{
int i=0,n;
ElemType temp;
DulNode *s,*p;
p=(*L)->next;
printf("請輸入插入元素數量：\n");
scanf("%d",&n);
count=n;
printf("請輸入%d個自然數\n",n);
while(i<n)
{
scanf("%d",&temp);
s=(DulNode*)malloc(sizeof(DulNode));
s->data=temp;
while((p!=(*L))&&(p->data<temp))//查找所要插入的位置
{
p=p->next;
}

s->prior=p->prior;//新節點的插入
s->next=p;
p->prior->next=s;
p->prior=s;

p=(*L)->next;//將指針回指到鏈表第一個非空節點，主要是為了下次查找插入位置
i++;
}
}
void Display(DulLinkList L)
{
DulNode *p;
p=L->next;
printf("雙向鏈表中的數據為:\n");
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void Sort(DulLinkList *L)
{
ElemType temp;
DulNode *p,*q;
p=(*L)->next;
q=(*L)->prior;
if(count%2!=0)
q=q->prior;
p=p->next;

while(p!=q)
{
temp=p->data;
p->data=q->data;
q->data=temp;

p=p->next;

if(p!=q) //第二題只需交換節點數據
q=q->prior;//這幾個if else語句需要仔細
else
break;
if(p!=q)
p=p->next;
else
break;
if(p!=q)
q=q->prior;
else
break;
}

}
void main()
{
DulLinkList L;
InitDLList(&L);//初始化鏈表
ListInsert(&L);//順序插入數據
Display(L);//顯示結果
Sort(&L);//第二題操作
Display(L);//第二題輸出結果
}

㈡ C語言、雙向鏈表

#include <stdio.h>
#include <string.h>
struct person
{
char name[10];
int number;
person *next;
person *last;
};person *p,*q,*start=NULL,*end;void insert(int num,char nam[10])//插入函數,按姓名的首字母順序插入鏈表中的。
{
q=new person;
if (start==NULL) //判斷start是否為空 若空則新建
{
start=q;
end=q;
p=q;
start->last=NULL;
end->next=NULL;
}
else
{

if(strcmp(nam,start->name)<=0)//插入鏈表頭
{
start->last=q;
q->next=start;
q->last=NULL;
start=q;
}
else if (strcmp(nam,end->name)>0) //插入表尾部
{
end->next=q;
q->last=end;
end=q;
q->next=NULL;
}
else if (strcmp(nam,end->name)<0&&strcmp(nam,start->name)>0)//插入鏈表中
{
for (p=start;strcmp(nam,p->name)>0;p=p->next);
q->next=p;
p->last=q;
for (p=start;p->next!=q->next;p=p->next);
p->next=q;
q->last=p;
}

}
strcpy(q->name,nam);
q->number=num;

}
void find(int num) //按編號查找
{
if(start==NULL)
{
printf("無記錄\n");
}
else
{
for(p=start;p!=NULL&&p->number!=num;p=p->next);
if(p==NULL)
{
printf("不存在的編號!\n");

}
else if (p->number==num)
{
printf("您查找的編號是:%d\n",num);
printf("該生的姓名為:%s",p->name);
}

}
} void del(int num) //按編號刪除
{
for(p=start;p->number!=num;p=p->next);
if (p->number==num)
{
if (p->next==NULL)
{
if(p->last==NULL)
{
start=NULL;

}
else
{
(p->last)->next=NULL;
}
delete p;
}
else if (p->last==NULL)
{
(p->next)->last=NULL;
start = p->next;
delete p;
}
else if(p->last!=NULL&&p->next!=NULL)
{
(p->last)->next=p->next;
(p->next)->last=p->last;
delete p;
}
}

else
{
printf("不存在的編號!\n");
}

}void show()
{
printf("學號\t姓名\n");
for (p=start;;p=p->next)
{
printf("%d\t%s\n",p->number,p->name);
if (p->next==NULL)
break;
}
}void main()
{
int i,num;
char nam[10];
printf("輸入三位學生信息（學號，姓名）:");
for(i=0;i<3;i++)
{
scanf("%d%s",&num,nam);
insert(num,nam);
}
show();

printf("輸入要刪除的學生的學號:");
scanf("%d",&num);
del(num);
show();
printf("輸入要查找的學生的學號:");
scanf("%d",&num);
find(num);
//show();
}

㈢ 雙向鏈表排序c語言程序設計

/************************************************************************/
/*
	文件名		doublelnk.h
	作用			定義必要的結構體，並對雙向鏈表的操作函數做聲明
*/
/************************************************************************/

#ifndefDList_H
#defineDList_H
typedefintItem;
typedefstructNode*PNode;
typedefPNodePosition;
/*定義節點類型*/
typedefstructNode
{
	Itemid;		/*編號*/
	Itemdata;		/*數據域*/
	PNodeprevious;/*指向前驅*/
	PNodenext;		/*指向後繼*/
}Node;
/*定義鏈表類型*/
typedefstruct
{
	PNodehead;		/*指向頭節點*/
	PNodetail;		/*指向尾節點*/
	intsize;
}DList;

enumenumSortType
{
	ID,
	DATA
};

/*分配值為i的節點，並返回節點地址*/
PositionMakeNode(Itemid,Itemdata);

/*釋放p所指的節點*/
voidFreeNode(PNodep);

/*構造一個空的雙向鏈表*/
DList*InitList();

/*摧毀一個雙向鏈表*/
voidDestroyList(DList*plist);

/*將一個鏈表置為空表，釋放原鏈表節點空間*/
voidClearList(DList*plist);

/*返回頭節點地址*/
PositionGetHead(DList*plist);

/*返回尾節點地址*/
PositionGetTail(DList*plist);

/*返回鏈表大小*/
intGetSize(DList*plist);

/*返回p的直接後繼位置*/
PositionGetNext(Positionp);

/*返回p的直接前驅位置*/
PositionGetPrevious(Positionp);

/*將pnode所指節點插入第一個節點之前*/
PNodeInsFirst(DList*plist,PNodepnode);

/*將鏈表第一個節點刪除並返回其地址*/
PNodeDelFirst(DList*plist);

/*獲得節點的數據項*/
ItemGetItem(Positionp);

/*設置節點的數據項*/
voidSetItem(Positionp,Itemi);

/*刪除鏈表中的尾節點並返回其地址，改變鏈表的尾指針指向新的尾節點*/
PNodeRemove(DList*plist);

/*在鏈表中p位置之前插入新節點S*/
PNodeInsBefore(DList*plist,Positionp,PNodes);

/*在鏈表中p位置之後插入新節點s*/
PNodeInsAfter(DList*plist,Positionp,PNodes);

/*返回在鏈表中第i個節點的位置*/
PNodeLocatePos(DList*plist,inti);

voidListTraverse(DList*plist,void(*visit)(Node));

/*對雙向鏈表按照執行的排序方式進行排序*/
voidSortDLnk(DList*plist,enumSortTypesortType);

voidSortDLnkbyID(DList*plist);
voidSortDLnkbyData(DList*plist);
voidswapnode(PNodeanode,PNodebnode);
#endif


/************************************************************************/
/*
	文件名		doublelnk.cpp
	作用			對雙向鏈表的操作函數進行具體實現
*/
/************************************************************************/
#include"doublelnk.h"
#include<malloc.h>
#include<stdlib.h>


/*分配值為i的節點，並返回節點地址*/
PositionMakeNode(Itemid,Itemdata)
{
	PNodep=NULL;
	p=(PNode)malloc(sizeof(Node));
	if(p!=NULL)
	{
		p->id=id;
		p->data=data;
		p->previous=NULL;
		p->next=NULL;
	}	
	returnp;
}

/*釋放p所指的節點*/
voidFreeNode(PNodep)
{
	free(p);
}

/*構造一個空的雙向鏈表*/
DList*InitList()
{
	DList*plist=(DList*)malloc(sizeof(DList));
	PNodehead=MakeNode(0,0);
	if(plist!=NULL)
	{
		if(head!=NULL)
		{
			plist->head=head;
			plist->tail=head;
			plist->size=0;
		}
		else
			returnNULL;
	}
	returnplist;
}

/*摧毀一個雙向鏈表*/
voidDestroyList(DList*plist)
{
	ClearList(plist);
	free(GetHead(plist));
	free(plist);
}

/*判斷鏈表是否為空表*/
intIsEmpty(DList*plist)
{
	if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))
		return1;
	else
		return0;
}
/*將一個鏈表置為空表，釋放原鏈表節點空間*/
voidClearList(DList*plist)
{
	PNodetemp,p;
	p=GetTail(plist);
	while(!IsEmpty(plist))
	{	
		temp=GetPrevious(p);
		FreeNode(p);
		p=temp;
		plist->tail=temp;
		plist->size--;
	}
}

/*返回頭節點地址*/
PositionGetHead(DList*plist)
{
	returnplist->head;
}

/*返回尾節點地址*/
PositionGetTail(DList*plist)
{
	returnplist->tail;
}

/*返回鏈表大小*/
intGetSize(DList*plist)
{
	returnplist->size;
}

/*返回p的直接後繼位置*/
PositionGetNext(Positionp)
{
	returnp->next;
}

/*返回p的直接前驅位置*/
PositionGetPrevious(Positionp)
{
	returnp->previous;
}

/*將pnode所指節點插入第一個節點之前*/
PNodeInsFirst(DList*plist,PNodepnode)
{
	Positionhead=GetHead(plist);

	if(IsEmpty(plist))
		plist->tail=pnode;
	plist->size++;

	pnode->next=head->next;
	pnode->previous=head;

	if(head->next!=NULL)
		head->next->previous=pnode;
	head->next=pnode;

	returnpnode;
}

/*將鏈表第一個節點刪除,返回該節點的地址*/
PNodeDelFirst(DList*plist)
{
	Positionhead=GetHead(plist);
	Positionp=head->next;
	if(p!=NULL)
	{
		if(p==GetTail(plist))
			plist->tail=p->previous;
		head->next=p->next;
		head->next->previous=head;
		plist->size--;

	}	
	returnp;
}

/*獲得節點的數據項*/
ItemGetItem(Positionp)
{
	returnp->data;
}

/*設置節點的數據項*/
voidSetItem(Positionp,Itemi)
{
	p->data=i;
}

/*刪除鏈表中的尾節點並返回地址，改變鏈表的尾指針指向新的尾節點*/
PNodeRemove(DList*plist)
{
	Positionp=NULL;
	if(IsEmpty(plist))
		returnNULL;
	else
	{
		p=GetTail(plist);
		p->previous->next=p->next;
		plist->tail=p->previous;
		plist->size--;
		returnp;
	}
}
/*在鏈表中p位置之前插入新節點s*/
PNodeInsBefore(DList*plist,Positionp,PNodes)
{
	s->previous=p->previous;
	s->next=p;
	p->previous->next=s;	
	p->previous=s;

	plist->size++;
	returns;
}
/*在鏈表中p位置之後插入新節點s*/
PNodeInsAfter(DList*plist,Positionp,PNodes)
{
	s->next=p->next;
	s->previous=p;

	if(p->next!=NULL)
		p->next->previous=s;
	p->next=s;

	if(p=GetTail(plist))
		plist->tail=s;

	plist->size++;
	returns;
}

/*返回在鏈表中第i個節點的位置*/
PNodeLocatePos(DList*plist,inti)
{
	intcnt=0;
	Positionp=GetHead(plist);
	if(i>GetSize(plist)||i<1)
		returnNULL;

	while(++cnt<=i)
	{
		p=p->next;
	}

	returnp;
}

/*依次對鏈表中每個元素調用函數visit()*/
voidListTraverse(DList*plist,void(*visit)(Node))
{
	Positionp=GetHead(plist);
	if(IsEmpty(plist))
		exit(0);
	else
	{

		while(p->next!=NULL)
		{
			p=p->next;
			visit(*p);
		}
	}
}


voidSortDLnk(DList*plist,enumSortTypesortType)
{
	switch(sortType)
	{
	caseID:
		SortDLnkbyID(plist);
		break;
	caseDATA:
		SortDLnkbyData(plist);
		break;
	}
}

voidSortDLnkbyID(DList*plist)
{
	PNodehead=plist->head;
	Nodetmpnode;
	Positioncurrnode=head;
	Positionbianlinode;
	while((currnode=currnode->next)!=NULL)
	{
		bianlinode=currnode;
		while((bianlinode=bianlinode->next)!=NULL)
		{
			if(currnode->id>bianlinode->id)
			{
				swapnode(currnode,bianlinode);
			}			
		}
	}	
}

voidSortDLnkbyData(DList*plist)
{
	PNodehead=plist->head;
	Nodetmpnode;
	Positioncurrnode=head;
	Positionbianlinode;
	while((currnode=currnode->next)!=NULL)
	{
		bianlinode=currnode;
		while((bianlinode=bianlinode->next)!=NULL)
		{
			if(currnode->data>bianlinode->data)
			{
				swapnode(currnode,bianlinode);
			}			
		}
	}	
}

voidswapnode(PNodeanode,PNodebnode)
{//這裡面要特別注意防止前驅節點是頭結點和後驅節點是Null的情況
	Nodetmpnode;
	tmpnode.id=anode->id;
	tmpnode.data=anode->data;

	anode->id=bnode->id;
	anode->data=bnode->data;

	bnode->id=tmpnode.id;
	bnode->data=tmpnode.data;
}/************************************************************************/
/*
	文件名		program.cpp
	作用			對雙向鏈表的操作函數進行測試
*/
/************************************************************************/

#include"doublelnk.h"
#include<stdio.h>
voidprint(Nodenode)
{
	printf("數據項:id=%d,data=%d
",node.id,node.data);
}
intmain()
{
	DList*plist=NULL;
	PNodep=NULL;

	plist=InitList();
	p=InsFirst(plist,MakeNode(12,23));
	InsBefore(plist,p,MakeNode(2,54));
	InsAfter(plist,p,MakeNode(3,34));

	printf("p前驅位置的值為%d
",GetItem(GetPrevious(p)));
	printf("p位置的值為%d
",GetItem(p));
	printf("p後繼位置的值為%d
",GetItem(GetNext(p)));


	printf("遍歷輸出各節點數據項:
");
	ListTraverse(plist,print);

	printf("按照ID排序後遍歷輸出:
");
	SortDLnk(plist,ID);
	ListTraverse(plist,print);

	printf("按照Data排序後遍歷輸出:
");
	SortDLnk(plist,DATA);
	ListTraverse(plist,print);

	printf("除了頭節點該鏈表共有%d個節點
",GetSize(plist));
	FreeNode(DelFirst(plist));
	printf("刪除第一個節點後重新遍歷輸出為:
");
	ListTraverse(plist,print);
	printf("除了頭節點該鏈表共有%d個節點
",GetSize(plist));

	DestroyList(plist);
	printf("鏈表已被銷毀
");

	return0;
}

程序總共分三部分， 分別是雙向鏈表的頭文件、源文件和測試程序

建立工程後，分別建立相應的文件並添加相應代碼應該就可以

下面的圖片是我的運行效果（聲明：程序中很多代碼參考了以為前輩的代碼http://blog.csdn.net/hopeyouknow/article/details/6716177）

㈣ 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語言創建雙向鏈表順時針數到n刪除一個節點，逆時針數到m刪除一個節點，輸出只有一個節點時節點數值

#include<stdio.h>
#include<stdlib.h>
structcyclechain{
structcyclechain*pre;
structcyclechain*next;
unsignedintmessage;
};
typedefstructcyclechainCC;//定義鏈表節點結構
CC*entry=NULL;//環鏈表入口
voidcreatchain(unsignedintm)//建立自然數環鏈
{
CC*lastnode;
unsignedinti;
if(entry==NULL){
entry=(CC*)malloc(sizeof(CC));
entry->pre=entry;
entry->next=entry;
entry->message=1;
}
lastnode=entry;
for(i=2;i<=m;i++){
lastnode->next=(CC*)malloc(sizeof(CC));
lastnode->next->pre=lastnode;
lastnode->next->message=i;
lastnode=lastnode->next;
}
entry->pre=lastnode;
lastnode->next=entry;
}

voidposdel(unsignedintn,CC*entrynode,CC**presentnode)//正向刪除，最後個參數代表刪除後，節點位置
{
while(--n){
entrynode=entrynode->next;
}
*presentnode=entrynode->pre;
printf("posdelmessage:%d
",entrynode->message);
entrynode->pre->next=entrynode->next;
entrynode->next->pre=entrynode->pre;
free(entrynode);
}

voidnegdel(unsignedintk,CC*entrynode,CC**presentnode)//反向刪除，最後個參數代表刪除後，節點位置
{
while(--k){
entrynode=entrynode->pre;
}
*presentnode=entrynode->next;
printf("negdelmessage:%d
",entrynode->message);
entrynode->pre->next=entrynode->next;
entrynode->next->pre=entrynode->pre;
free(entrynode);

}
unsignedcharcheckchain(CC*entry)//判定是否為鏈表最後一個元素
{
if(entry->pre==entry)return1;
elsereturn0;
}

intmain()
{
CC*presentnode;
creatchain(6);//創建鏈表
presentnode=entry;
//一直刪除元素，直到只剩一個元素
while(1){
if(checkchain(presentnode))//檢測是否為最後個元素
break;
posdel(3,presentnode,&presentnode);
if(checkchain(presentnode))
break;
negdel(4,presentnode,&presentnode);
if(checkchain(presentnode))
break;
}
printf("result:%d
",presentnode->message);
free(presentnode);//釋放最後個節點的堆內存
return0;
}

沒做函數參數安全性處理，樓主自己改改