本文目錄一覽：
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）。如果要想找到這一排中某個目標人，從任意一個人開始，可以沿左手方向嘗試查找，如果找不到，可以繼續沿右手方向查找，直到找到目標人。
循環雙向鏈表是這樣的：若干個人圍成一圈，每個人都抬起左手指向他左邊的人，並且每個人都抬起右手指向他右邊的人，這樣每個人的左右手都可以指到一個人（如果只有一個人，那麼他的左右手都指向自己）。無論選擇左手方向還是右手方向，都可以不停地循環找到每一個人。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/271866.html
微信掃一掃 
支付寶掃一掃 