雙向鏈表c語言
1. c語言 雙向鏈表 快速排序
我說一下想法你看行不行
直接在鏈表中排序太麻煩，不如把關鍵字和指針單獨抽取出來放到一個結構體數組中
然後對這個數組進行排序，排好後按相應指針順序輸出鏈表元素即可
在輸入規模不大的情況下增加了一些空間代價，但是卻可使代碼簡化不少，應該是可行的。
當然直接交換雙向鏈表中的兩個元素也非難事。
2. c語言什麼單向鏈表，什麼是雙向鏈表
單向就是， 只可以從頭到尾按指針向一個方向遍歷，不可以返過來。
雙向就是，任何時候，從前往後，還是從後往前都可以遍歷，兩個方向都有指針
雙向循環， 就是一個鏈表頭尾相連，指針也是雙方向的，可以從頭遍歷到尾，再回到頭，或者從尾到頭遍歷，再回到尾
3. 雙向鏈表的排序...（用c語言編寫程序）
#include
#include
struct node
{
int data;
struct node* next;
struct node* prev;
};
struct node* create_list(int n)
{
struct node *head = null;
struct node *p = null, *q = null;
int i = 0, data = 0;
for (i = 0; i < n; i++)
{
printf("請輸入結點%d的值：", i+1);
scanf("%d", &data);
p = (struct node*)malloc(sizeof(struct node));
p->next = null;
p->data = data;
if (i == 0)
{
head = p;
p->prev = null;
}
else
{
p->prev = q;
q->next = p;
}
q = p;
}
return head;
}
void free_list(struct node* head)
{
struct node* p = head;
struct node* q = null;
while (p != null)
{
q = p;
p = p->next;
delete q;
}
}
void display_list(struct node* head)
{
struct node* p = head;
while (p != null)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
struct node* get_max_node(struct node* node)
{
struct node* max_node = node;
while (node != null)
{
if (node->data > max_node->data)
{
max_node = node;
}
node = node->next;
}
return max_node;
}
void swap_node(struct node* node1, struct node* node2)
{
int temp;
if (node1 == node2)
{
return;
}
temp = node1->data;
node1->data = node2->data;
node2->data = temp;
}
void sort_list(struct node* head)
{
struct node* max_node = null;
struct node* current = null;
current = head;
while (current != null)
{
max_node = get_max_node(current);
swap_node(current, max_node);
current = current->next;
}
}
int main()
{
struct node *head = null;
int n = 0;
printf("請輸入雙向鏈表的結點個數：");
scanf("%d", &n);
head = create_list(n);
display_list(head);
sort_list(head);
display_list(head);
free_list(head);
return 0;
}
4. 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);//第二題輸出結果
}
5. 雙向鏈表排序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）
6. C語言定義雙向鏈表結構體
struct
node
{
DataType
data;
node
*
prior;
node
*
next;
};
其中prior指針用來存儲前一節點的地址，next用來存儲後一節點的地址，就比單項鏈表多了一個指針而已，可以添加其它自定義的數據成員
7. 求問c語言單向鏈表和雙向鏈表與循環鏈表的區別
打個比方。把鏈表節點看作是一個人，把鏈表指針看作是人的手（左手是前向指針，右手是後向指針）。
非循環的單向鏈表是這樣的：若干個人排成一排，每個人都抬起右手指向他右邊的人，最右邊的人的右手指向了空氣（NULL）。如果要想找到這一排中任意一個人，必須從排頭（鏈表頭）開始沿手指的方向挨個查找。
循環單向鏈表是這樣的：若干個人圍成一圈，每個人都抬起右手指向他右邊的人，這樣每個人的右手都能指到一個人（如果只有一個人，那麼他的右手指向自己）。從任意一個人開始，沿著手指的方向，可以不停地循環找到每一個人。
非循環的雙向鏈表是這樣的：若干個人排成一排，每個人都抬起左手指向他左邊的人，並且每個人都抬起右手指向他右邊的人，那麼最左邊的人的左手指向了空氣（NULL），最右邊的人的右手指向了空氣（NULL）。如果要想找到這一排中某個目標人，從任意一個人開始，可以沿左手方向嘗試查找，如果找不到，可以繼續沿右手方向查找，直到找到目標人。
循環雙向鏈表是這樣的：若干個人圍成一圈，每個人都抬起左手指向他左邊的人，並且每個人都抬起右手指向他右邊的人，這樣每個人的左右手都可以指到一個人（如果只有一個人，那麼他的左右手都指向自己）。無論選擇左手方向還是右手方向，都可以不停地循環找到每一個人。
8. 使用C語言實現雙向鏈表的建立、刪除和插入
#include<stdio.h>
#include<stdlib.h>
#include<malloc.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;i<3;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);
}