單鏈c語言
『壹』 c語言創建單鏈表問題
你的代碼很有問題啊。在VS2013上面跑都不能跑。
你的意思是如果不讀取到May就一直往下讀取建立鏈表吧。
幫你修改了一下。應該可以了。
測試環境：DevC++
測試程序
#include<stdio.h>
#include<string.h>
#include"malloc.h"
#definelensizeof(link)
typedefstructlinklist
{chara[4];
structlinklist*next;
}link;
main()
{
link*head=(link*)malloc(len);
link*p,*q;
memset(head->a,' ',sizeof(char)*4);
head->next=NULL;
scanf("%s",head->a);
q=head;
while(strcmp(q->a,"May")!=0){
p=(link*)malloc(len);
q->next=p;
q=p;
scanf("%s",p->a);
}
p->next=NULL;
}
『貳』 單鏈表問題用C語言編寫
用一組地址任意的存儲單元存放線性表中的數據元素。
以元素(數據元素的映象)
+ 指針(指示後繼元素存儲位置)
= 結點
(表示數據元素 或 數據元素的映象)
以「結點的序列」表示線性表
�8�7�8�7 稱作線性鏈表（單鏈表）
單鏈表是一種順序存取的結構，為找第 i 個數據元素，必須先找到第 i-1 個數據元素。
因此，查找第 i 個數據元素的基本操作為：移動指針，比較 j 和 i
單鏈表
1、鏈接存儲方法
鏈接方式存儲的線性表簡稱為鏈表（Linked List）。
鏈表的具體存儲表示為：
① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的）
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）
注意：
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
2、鏈表的結點結構
┌──┬──┐
│data│next│
└──┴──┘
data域--存放結點值的數據域
next域--存放結點的直接後繼的地址（位置）的指針域（鏈域）
注意：
①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。
②每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。
【例】線性表（bat，cat，eat，fat，hat，jat，lat，mat）的單鏈表示如示意圖
3、頭指針head和終端結點指針域的表示
單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。
注意：
鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。
【例】頭指針名是head的鏈表可稱為表head。
終端結點無後繼，故終端結點的指針域為空，即NULL。
4、單鏈表的一般圖示法
由於我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。
5、單鏈表類型描述
typedef char DataType; //假設結點的數據域類型為字元
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意：
①LinkList和ListNode *是不同名字的同一個指針類型（命名的不同是為了概念上更明確）
②LinkList類型的指針變數head表示它是單鏈表的頭指針
③ListNode *類型的指針變數p表示它是指向某一結點的指針
6、指針變數和結點變數
┌────┬────────────┬─────────────┐
││指針變數│結點變數 │
├────┼────────────┼─────────────┤
│ 定義 │在變數說明部分顯式定義 │在程序執行時，通過標准 │
│ │ │函數malloc生成 │
├────┼────────────┼─────────────┤
│ 取值 │ 非空時，存放某類型結點 │實際存放結點各域內容 │
│ │的地址 │ │
├────┼────────────┼─────────────┤
│操作方式│ 通過指針變數名訪問 │ 通過指針生成、訪問和釋放 │
└────┴────────────┴─────────────┘
①生成結點變數的標准函數
p=( ListNode *)malloc(sizeof(ListNode))；
//函數malloc分配一個類型為ListNode的結點變數的空間,並將其首地址放入指針變數p中
②釋放結點變數空間的標准函數
free(p)；//釋放p所指的結點變數空間
③結點分量的訪問
利用結點變數的名字*p訪問結點分量
方法一：(*p).data和(*p).next
方法二：p-﹥data和p-﹥next
④指針變數p和結點變數*p的關系
指針變數p的值——結點地址
結點變數*p的值——結點內容
(*p).data的值——p指針所指結點的data域的值
(*p).next的值——*p後繼結點的地址
*((*p).next)——*p後繼結點
注意：
① 若指針變數p的值為空（NULL），則它不指向任何結點。此時，若通過*p來訪問結點就意味著訪問一個不存在的變數，從而引起程序的錯誤。
② 有關指針類型的意義和說明方式的詳細解釋
可見，在鏈表中插入結點只需要修改指針。但同時，若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。
因此，在單鏈表中第 i 個結點之前進行插入的基本操作為:
找到線性表中第i-1個結點，然後修改其指向後繼的指針。
#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define Status inttypedef int ElemType;/*此處利用#define或typedef 將ElemType先作定義*//*此處需補充定義鏈表的結構類型聲明*/LinkList InitList(){LinkList head;</p><p>head=(LinkList)malloc(sizeof(LNode));</p><p>head->next=NULL;</p><p>return head;}void printlist(LinkList L) //這是一個輸出表元的函數{LinkList p;</p><p>p=L->next;</p><p>while(p!=NULL)</p><p>{補充一條語句；</p><p>補充一條語句；}}void CreateListF(LinkList &L , int n ) // 單號的同學用頭插法建表{ /* 補充N條語句，實現用值來建表 */ } void CreateListR(LinkList &L , int n ) // 雙號的同學用尾插法建表{ /* 補充N條語句，實現用值來建表 */ } /*補充一個演算法函數，查找表中值為X元素 */void main(){LinkList y;</p><p>int n;</p><p>printf("請輸入N的值，它代表y中元素個數：");</p><p>scanf("%d",&n);</p><p>printf("\n");</p><p>/*此處調用上面的建表函數*/</p><p>printf("\n");</p><p>printf("這是鏈表y中的元素：");</p><p>/*此處調用上面的函數輸出y表中的元素 */</p><p>printf("\n\n\n");</p><p></p><p>/*此處要補充語句，調用上面的查找表元素的函數*/</p><p></p><p>printf("\n\n\n");</p><p></p><p></p><p>}
『叄』 數據結構(C語言) 單鏈表的合並(100分)
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct LNode
{
int data;
struct LNode *next;
};
typedef LNode* LinkList;
Linklist *unio(Linklist *p,Linklist *q) //合並
{
linklist *R,*pa,*qa,*ra;
pa=p;
qa=q;
R=ra=p;
while(pa->next!=NULL&&qa->next!=NULL)
{
if(pa->data>qa->data)
{
ra->next=qa;
qa=qa->next;
}
else
{
ra->next=pa;
pa=pa->next;
}
}
if(pa->next!=NULL)
ra->next=pa;
if(qa->next!=NULL)
ra->next==qa;
return R;
}
void CreateList_L(LinkList &L, int n)
{ // 演算法2.11
// 逆位序輸入（隨機產生）n個元素的值，建立帶表頭結點的單鏈線性表L
LinkList p;
int i;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 先建立一個帶頭結點的單鏈表
for (i=n; i>0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); // 生成新結點
p->data = rand() % 200; // 改為一個隨機生成的數字(200以內)
p->next = L->next;
L->next = p; // 插入到表頭
}
} // CreateList_L
void main()
{
LinkList pHead; //定義兩個鏈表
LinkList qHead;
int num;
printf("輸入要創建的鏈表長度num\n");
scanf("d%",&num);
CreateList_L(pHead,num);
CreateList_L(qHead,num);
LinkList p=pHead->next;
LinkList q=qHead->next;
while(p!=NULL) //下面是輸出兩個鏈表
{
printf("%d\n",p->data);
p=p->next;
}
while(q!=NULL)
{
printf("%d\n",q->data);
q=q->next;
}
//上面創建完後，下面合並並輸出
LinkList unioHead;
unioHead unio(&pHead,&qHead); //合並
LinkList myunio = unioHead ->next;
while(myunio!=NULL) //輸出
{
printf("%d\n",myunio->data);
myunio=myunio->next;
}
}
『肆』 數據結構單鏈表實驗(c語言版)
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;/* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據實際情況而定，這里假設為int */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定義LinkList */
/* 初始化順序線性表 */
Status InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node)); /* 產生頭結點,並使L指向此頭結點 */
if(!(*L)) /* 存儲分配失敗 */
return ERROR;
(*L)->next=NULL; /* 指針域為空 */
return OK;
}
/* 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
Status ListEmpty(LinkList L)
{
if(L->next)
return FALSE;
else
return TRUE;
}
/* 初始條件：順序線性表L已存在。操作結果：將L重置為空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一個結點 */
while(p) /* 沒到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 頭結點指針域為空 */
return OK;
}
/* 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數 */
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; /* p指向第一個結點 */
while(p)
{
i++;
p=p->next;
}
return i;
}
/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數據元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 聲明一結點p */
p = L->next; /* 讓p指向鏈表L的第一個結點 */
j = 1; /* j為計數器 */
while (p && j<i) /* p不為空或者計數器j還沒有等於i時，循環繼續 */
{
p = p->next; /* 讓p指向下一個結點 */
++j;
}
if ( !p || j>i )
return ERROR; /* 第i個元素不存在 */
*e = p->data; /* 取第i個元素的數據 */
return OK;
}
/* 初始條件：順序線性表L已存在 */
/* 操作結果：返回L中第1個與e滿足關系的數據元素的位序。 */
/* 若這樣的數據元素不存在，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(p->data==e) /* 找到這樣的數據元素 */
return i;
p=p->next;
}
return 0;
}
/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j < i) /* 尋找第i個結點 */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* 第i個元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 生成新結點(C語言標准函數) */
s->data = e;
s->next = p->next; /* 將p的後繼結點賦值給s的後繼 */
p->next = s; /* 將s賦值給p的後繼 */
return OK;
}
/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i) /* 遍歷尋找第i個元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* 第i個元素不存在 */
q = p->next;
p->next = q->next; /* 將q的後繼賦值給p的後繼 */
*e = q->data; /* 將q結點中的數據給e */
free(q); /* 讓系統回收此結點，釋放內存 */
return OK;
}
/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個數據元素輸出 */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
/* 隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（頭插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化隨機數種子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; /* 先建立一個帶頭結點的單鏈表 */
for (i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /* 生成新結點 */
p->data = rand()%100+1; /* 隨機生成100以內的數字 */
p->next = (*L)->next;
(*L)->next = p; /* 插入到表頭 */
}
}
/* 隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
srand(time(0)); /* 初始化隨機數種子 */
*L = (LinkList)malloc(sizeof(Node)); /* L為整個線性表 */
r=*L; /* r為指向尾部的結點 */
for (i=0; i<n; i++)
{
p = (Node *)malloc(sizeof(Node)); /* 生成新結點 */
p->data = rand()%100+1; /* 隨機生成100以內的數字 */
r->next=p; /* 將表尾終端結點的指針指向新結點 */
r = p; /* 將當前的新結點定義為表尾終端結點 */
}
r->next = NULL; /* 表示當前鏈表結束 */
}
int main()
{
LinkList L;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L後：ListLength(L)=%d\n",ListLength(L));
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表頭依次插入1～5後：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
i=ClearList(&L);
printf("清空L後：ListLength(L)=%d\n",ListLength(L));
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10後：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
ListInsert(&L,1,0);
printf("在L的表頭插入0後：L.data=");
ListTraverse(L);
printf("ListLength(L)=%d \n",ListLength(L));
GetElem(L,5,&e);
printf("第5個元素的值為：%d\n",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d個元素的值為%d\n",k,j);
else
printf("沒有值為%d的元素\n",j);
}
k=ListLength(L); /* k為表長 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 刪除第j個數據 */
if(i==ERROR)
printf("刪除第%d個數據失敗\n",j);
else
printf("刪除第%d個的元素值為：%d\n",j,e);
}
printf("依次輸出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 刪除第5個數據 */
printf("刪除第%d個的元素值為：%d\n",j,e);
printf("依次輸出L的元素：");
ListTraverse(L);
i=ClearList(&L);
printf("\n清空L後：ListLength(L)=%d\n",ListLength(L));
CreateListHead(&L,20);
printf("整體創建L的元素(頭插法)：");
ListTraverse(L);
i=ClearList(&L);
printf("\n刪除L後：ListLength(L)=%d\n",ListLength(L));
CreateListTail(&L,20);
printf("整體創建L的元素(尾插法)：");
ListTraverse(L);
return 0;
}
『伍』 求大神幫忙。c語言，求單鏈表的長度。
typedef
struct
LNode
{
int
date;
struct
LNode
*next;
}
LNode,
*LinkList;
/*線性鏈表類型
*/
typedef
int
Status;
int
CreatLinkList_L(LinkList
&L)/*逆位序輸入n個元素的值，建立帶頭節點的單鏈線性表L
*/
{
int
i,n;
printf("輸入n的值");
scanf("%d",&n);
LinkList
p,
p2;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;/*先建立一個帶頭節點的單鏈表*/
p2
=
L;
for(i=n;i>0;--i)
{
p
=
(LinkList)malloc(sizeof(LNode));
scanf("%d",&(p->date));
p->next
=
p2->next;
p2->next
=
p;
}
return
OK;
}
Status
ListLength_L(LinkList
L)
{
int
i=0;
LinkList
p
=
L;
p
=
p->next;
while(p!=NULL)
{
printf("%d\n",
p->date);
p
=
p->next;
i++;
}
return
i;
}
void
DeleteLinkList_L(LinkList
L)
{
LinkList
p
=
L->next;
while(p)
{
free(L);
L
=
p;
p
=
L->next;
}
}
void
main()
{
LinkList
L
=
NULL;
CreatLinkList_L(L);
printf("%d\n",
ListLength_L(L));
DeleteLinkList_L(L);//動態分配的內存應主動釋放
}
『陸』 數據結構（C語言）用單鏈表存儲一元多項式，並實現兩個多項式的相加運算，怎麼做
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
/*單項鏈表的聲明*/
typedef struct PolynNode{
int coef; // 系數
int expn; // 指數
struct PolynNode *next; }PolynNode,*PolynList;
/*正位序(插在表尾)輸入n個元素的值,建立帶表頭結構的單鏈線性表*/
/*指數系數一對一對輸入*/ void CreatePolyn(PolynList &L,int n)
{
int i;
下載
原文檔已轉碼為如下格式，以便移動設備查看
數據結構(c語言)用單鏈表存儲一元多項式,並實現兩個多項式的相加運算【最新】
閱讀：1037次 頁數：36頁 2016-03-21 舉報
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
/*單項鏈表的聲明*/
typedef struct PolynNode{
int coef; // 系數
int expn; // 指數
struct PolynNode *next; }PolynNode,*PolynList;
/*正位序(插在表尾)輸入n個元素的值,建立帶表頭結構的單鏈線性表*/
/*指數系數一對一對輸入*/ void CreatePolyn(PolynList &L,int n)
{
int i;
PolynList p,q;
L=(PolynList)malloc(sizeof(PolynNode)); // 生成頭結點
L->next=NULL;
q=L;
printf("成對輸入%d個數據 ",n);
for(i=1;i<=n;i++)
{
p=(PolynList)malloc(sizeof(PolynNode));
scanf("%d%d",&p->coef,&p->expn); //指數和系數成對輸入
q->next=p;
q=q->next;
}
p->next=NULL;
}
// 初始條件:單鏈表L已存在
// 操作結果: 依次對L的每個數據元素調用函數vi()。一旦vi()失敗,則操作失敗
void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType)) {
PolynList p=L->next;
while(p)
{
vi(p->coef, p->expn);
if(p->next)
{
printf(" + "); //「+」號的輸出,最後一項後面沒有「+」
}
p=p->next;
}
printf(" ");
}
/*ListTraverse()調用的函數(類型要一致)*/ void visit(ElemType c, ElemType e) {
if(c != 0)
{
printf("%dX^%d",c,e); //格式化輸出多項式每一項
}
}
/* 多項式相加,原理:歸並 */ /* 參數:兩個已經存在的多項式 */ /* 返回值:歸並後新的多項式的頭結點 */
PolynList MergeList(PolynList La, PolynList Lb) {
PolynList pa, pb, pc, Lc;
pa = La->next;
pb = Lb->next;
Lc = pc = La; // 用La的頭結點作為Lc的頭結點
while(pa&&pb)
{
if(pa->expn < pb->expn)
{
pc->next = pa; //如果指數不相等,pc指針連上指數小的結
點,
pc = pa;
pa = pa->next; //指向該結點的指針後移
}
else if (pa ->expn > pb->expn )
{
pc->next = pb; //pc指針連上指數小的結點,
pc = pb;
pb = pb->next; //指向該結點的指針後移
}
else //(pa ->expn = pb->expn )
{
pa->coef = pa->coef + pb->coef; //指數相等時,系數相加
pc->next = pa;
pc = pa;
pa = pa->next; //兩指針都往後移
pb = pb->next;
}
}
pc->next = pa ? pa:pb; // 插入剩餘段
return Lc;
}
void main()
{
PolynList ha,hb,hc;
printf("非遞減輸入多項式ha, ");
CreatePolyn(ha,5); // 正位序輸入n個元素的值
printf("非遞減輸入多項式hb, ");
CreatePolyn(hb,5); // 正位序輸入n個元素的值
『柒』 C語言的單鏈表問題，謝謝解答
單鏈表簡介
鏈表中的數據是以結點來表示的，每個結點的構成:元素(數據元素的映象) + 指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。
單鏈表
以"結點的序列"表示線性表稱作線性鏈表(單鏈表)
單鏈表是鏈式存取的結構，為找第 i 個數據元素，必須先找到第 i-1 個數據元素。
因此，查找第 i 個數據元素的基本操作為:移動指針，比較 j 和 i
單鏈表
1、鏈接存儲方法
鏈接方式存儲的線性表簡稱為鏈表(Linked List)。
鏈表的具體存儲表示為:
① 用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的，也可以是不連續的)
② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址(或位置)信息(稱為指針(pointer)或鏈(link))
注意:
鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。
2、鏈表的結點結構
┌───┬───┐
│data │next │
└───┴───┘
data域--存放結點值的數據域
next域--存放結點的直接後繼的地址(位置)的指針域(鏈域)
注意:
①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。
②每個結點只有一個鏈域的鏈表稱為單鏈表(Single Linked List)。
【例】線性表(bat，cat，eat，fat，hat，jat，lat，mat)的單鏈表示如示意圖
3、頭指針head和終端結點指針域的表示
單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。
注意:
鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。
終端結點無後繼，故終端結點的指針域為空，即NULL。
4、單鏈表的一般圖示法
由於我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指針，線性表(bat，cat，fat，hat，jat，lat，mat)的單鏈表就可以表示為下圖形式。
5、單鏈表類型描述
typedef char DataType; //假設結點的數據域類型為字元
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意:
①LinkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念上更明確)
②*LinkList類型的指針變數head表示它是單鏈表的頭指針
③ListNode類型的指針變數p表示它是指向某一結點的指針
6、指針變數和結點變數
指針變數
結點變數
定義
在變數說明部分顯式定義
在程序執行時，通過標准函數malloc生成
取值
非空時，存放某類型結點
實際存放結點各域內容的地址
①生成結點變數的標准函數
p=( ListNode *)malloc(sizeof(ListNode));
//函數malloc分配一個類型為ListNode的結點變數的空間,並將其首地址放入指針變數p中
②釋放結點變數空間的標准函數
free(p);//釋放p所指的結點變數空間
③結點分量的訪問
利用結點變數的名字*p訪問結點分量
方法一:(*p).data和(*p).next
方法二:p->data和p->next
④指針變數p和結點變數*p的關系
指針變數p的值--結點地址
結點變數*p的值--結點內容
(*p).data的值--p指針所指結點的data域的值
(*p).next的值--*p後繼結點的地址
*((*p).next)--*p後繼結點
注意:
① 若指針變數p的值為空(NULL)，則它不指向任何結點。此時，若通過*p來訪問結點就意味著訪問一個不存在的變數，從而引起程序的錯誤。
② 有關指針類型的意義和說明方式的詳細解釋
可見，在鏈表中插入結點只需要修改指針。但同時，若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。
因此，在單鏈表中第 i 個結點之前進行插入的基本操作為:
找到線性表中第i-1個結點，然後修改其指向後繼的指針。
『捌』 用C語言編寫建立一個從表尾到表頭逆向單鏈線性表且進行插入 刪除的程序
#include<iostream>
using
namespace
std;
struct
Linklist
{
int
data;
Linklist
*next;
};
Linklist
*L,*rear;
void
create()//尾插法建立鏈表
{
Linklist
*p;
int
x;
cout<<"輸入鏈表元素(按升序順序輸入)："
while(cin>>x&&x!=0)
{
if(L==NULL)
{
L=new
Linklist;
L->data=x;
rear=L;
L->next=NULL;
}
else
{
p=new
Linklist;
p->data=x;
rear->next=p;
p->next=NULL;
rear=p;
}
}
rear->next=NULL;
}
void
del(int
x)//刪除data域值為x的結點
{
Linklist
*p,*k,*t;
k=p=L;
while(p!=NULL)
{
if(p->data==x)
break;
k=p;
p=p->next;
}
if(p==L)
{
p=L;
L=L->next;
delete
p;
}
else
if(p==rear)
{
k->next=NULL;
delete
p;
}
else
if(p==NULL)
{
cout<<"沒有值為"<<x<<"的結點
"<<endl;
}
else
{
k->next=p->next;
delete
p;
}
}
void
insert(int
x)//插入data域值為x的結點(默認原鏈表為升序排列)
{
Linklist
*s,*p,*k;
s=new
Linklist;
s->data=x;
s->next=NULL;
k=p=L;
while(p!=NULL)
{
if(p->data>=x)
break;
k=p;
p=p->next;
}
if(p==L)
{
L=s;
s->next=p;
}
else
if(p==NULL)
{
k->next=s;
}
else
{
k->next=s;
s->next=p;
}
}
void
output()//將鏈表輸出
{
Linklist
*p;
p=L;
cout<<"鏈表中的元素為：";
while(p!=NULL)
{
cout<<p->data<<"
";
p=p->next;
}
cout<<endl<<endl;
}
void
LinkListDemo()
{
//
L是無頭結點的單鏈表
Linklist
*q,
*p,*t;//p指針用於指示原鏈表最後的結點（即an），q指針用於指示原來的頭結點（即a1）
q=L;
if
(
q
&&
q->next
)
{
t=q;//將q指針指向a1
L=L->next;//將L指針指向新鏈表的頭結點（即a2）
rear->next=q;
q->next=NULL;
t=NULL;
}
}
void
main()
{
create();
output();
int
x;
cout<<"輸入需要插入的元素：";
cin>>x;
insert(x);
output();
cout<<"輸入需要刪除的元素：";
cin>>x;
del(x);
output();
LinkListDemo();
output();
}
『玖』 c語言單鏈 之和
＃include<stdio.h>
＃include<malloc.h>
＃include<stdlib.h>
#define LEN sizeof(node)
typedef struct polynode /*用單鏈表存儲多項式的結點結構*/
{
int coef; /*多項式的系數*/
int exp; /*指數*/
struct polynode *next; /*next是struct polynode類型中的一個成員，它又指向
struct polynode類型的數據，以此建立鏈表*/
}node;/*若定為"node,*list;"，意即node*與list同為結構指針類型*/
node * create(void) /*指針函數，返回指針類型；用尾插法建立一元多項式的鏈表的函數*/
{
node *h,*r,*s;
int c,e;
h=(node *)malloc(LEN); /*建立多項式的頭結點，為頭結點分配存儲空間*/
r=h; /*r指針始終動態指向鏈表的當前表尾，以便於做尾插入，其初值指向頭結點*/
printf("coef:");
scanf("%d",&c); /*輸入系數*/
printf("exp: ");
scanf("%d",&e); /*輸入指針*/
while(c!=0) /*輸入系數為0時，表示多項式的輸入結束*/
{
s=(node *)malloc(LEN); /*申請新結點*/
s->coef=c; /*申請新結點後賦值*/
s->exp=e; /*申請新結點後賦值*/
r->next=s; /*做尾插，插入新結點*/
r=s; /*r始終指向單鏈表的表尾*/
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
}
r->next=NULL; /*將表的最後一個結點的next置NULL，以示表結束*/
return(h);
}
void polyadd(node *polya, node *polyb)/*一元多項式相加函數，用於將兩個多項式相加，然後將和多項式存放在多項式polya中，並將多項式ployb刪除*/
{
node *p,*q,*pre,*temp;
int sum;
p=polya->next;/*令p和q分別指向polya和polyb多項式鏈表中的第一個結點*/
q=polyb->next;
pre=polya; /*位置指針，指向和多項式polya*/
while(p!=NULL&&q!=NULL) /*當兩個多項式均未掃描結束時，執行以下操作*/
{
if(p->exp<q->exp) /*若p指向的多項式指數小於q指的指數*/
{
pre->next=p; /*將p結點加入到和多項式中*/
pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp) /*若指數相等，則相應的系數相加*/
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else /*如果系數和為零，則刪除結點p與q，並將指針指向下一個結點*/
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
else /*若p指數大於q指數*/
{
pre->next=q; /*p結點不動，將q結點加入到和多項式中*/
pre=pre->next;
q=q->next;
}
}
if(p!=NULL) /*多項式A中還有剩餘，則將剩餘的結點加入到和多項式中*/
pre->next=p;
else /*否則將B的結點加入到和多項式中*/
pre->next=q;
}
void print(node * p) /*輸出函數，列印出一元多項式*/
{
while(p->next!=NULL)
{
p=p->next;
printf(" %d*x^%d",p->coef,p->exp);
}
}
main() /*主函數*/
{
node * polya,* polyb;
printf("Welcome to use!\n");
printf("\nPlease input the ploya include coef && exp:\n");
polya=create(); /*調用建立鏈表函數，創建多項式A*/
print(polya);
printf("\nPlease input the ployb include coef && exp:\n");
polyb=create(); /*同理，創建B*/
print(polyb);
printf("\nSum of the poly is:\n");
polyadd(polya,polyb); /*調用一元多項式相加函數*/
print(polya); /*調用輸出函數，列印結果*/
printf("\n");