數據結構C語言實現——線性鏈表
declaration.h
#ifndef DECLARATION_H_INCLUDED
#define DECLARATION_H_INCLUDED
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define ElemType int
typedef ElemType* Triplet;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
#endif // DECLARATION_H_INCLUDED
function.h
#ifndef FUNCTION_H_INCLUDED
#define FUNCTION_H_INCLUDED
void CreateList_L(LinkList *L, int n);
//逆序輸入n個元素的值，簡歷帶頭結點的單鏈表L
Status ListInsert_L(LinkList *L , int i, ElemType e);
//在帶頭結點的單鏈線性表中第i個位置前插入元素e
Status ListDelete_L(LinkList *L, int i, ElemType e);
//在帶頭結點的單鏈線性表中，刪除第i個元素並由e返回其值
Status GetElem_L(LinkList L, int i, ElemType *e);
//L為帶頭結點的單鏈表的頭指針
//當第i個元素存在時將其值付給e並返回OK，否則返回ERROR
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc);
//歸並La和Lb表到Lc並按非遞減序列排列
void PrintList_L(LinkList L);
//輸出單鏈表中的內容
#endif // FUNCTION_H_INCLUDED
function.c
#include
#include
#include "declaration.h"
void CreateList_L(LinkList *L, int n)
{
Status i;
LinkList p;
*L=(LinkList)malloc (sizeof(LNode));
(*L)->next=NULL; //先建立帶頭結點的單鏈表;->的優先級比*高不要漏掉這裡的括號
for(i=n; i>0 ;i--)
{
p=(LinkList)malloc((sizeof(LNode)));//生成新節點
scanf("%d", &p->data);
p->next=(*L)->next; //插入到表頭
(* L)->next=p; // 數據是倒著插入連表的，即最後輸入的數在表頭
}
}//CreateList_L
Status ListInsert_L(LinkList *L , int i, ElemType e)
{
LinkList p=*L, s;
ElemType j=0;
while( p && j < i-1)
{
p=p->next;
j++;
}
if(!p || j >i-1) return ERROR; //i小於1或大於表長加1
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s; //先連接後插入
return OK;
}
Status ListDelete_L(LinkList *L, int i, ElemType *e)
{
LinkList p=*L, q;
ElemType j=0;
while(p->next && j < i-1)
{
p=p->next;
j++;
}
if( !(p->next) || j > i-1) return ERROR;//刪除位置不合理
q=p->next; p->next=q->next;
*e=q->data;
free(q);
return *e;
}
Status GetElem_L(LinkList L, int i, ElemType *e)
{
LinkList p;
ElemType j=1;
p=L->next;
while(p && jnext;
j++;
}
if( !p || j>i) return ERROR; //第i個元素不存在
*e=p->data;
return *e;
}//GetElem_L()
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)
{
//La和Lb兩個鏈表中數據非遞減排列
//歸並La和Lb表到Lc並按非遞減序列排列
LinkList pa, pb, pc;
int i=0,j=0;
pa=(*La)->next; pb=(*Lb)->next;
printf("%x %x",(int )pa,(int )pb);
(*Lc) =(LinkList)malloc(sizeof(LNode));
pc=(*Lc);
while( (int)pa && (int)pb)
{
if( (pa->data) <= (pb->data))
{
pc->next =pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
while( pa )
{
pc->next=pa;//插入剩余段
pc=pa;
pa=pa->next;
}
while( pb)
{
pc->next=pb;
pc=pb=NULL;
}
return OK;
}//MergeList_L()
void PrintList_L(LinkList L)
{
LinkList p;
for(p=L->next;p;p=p->next)//L為鏈表的頭結點數據域沒有賦值
printf("%d ",p->data);
printf("\n");
}
main.c
#include
#include
#include "declaration.h"
#include "function.h"
int main()
{
ElemType e;
LinkList *La, *Lb, *Lc;
La=(LinkList *)malloc(sizeof(LinkList));
Lb=(LinkList *)malloc(sizeof(LinkList));
Lc=(LinkList *)malloc(sizeof(LinkList));
printf("create la ,please enter 5 number:");
CreateList_L(La, 5);
printf("la=");
PrintList_L(*La);
printf("la表中第3個數是%d\n", GetElem_L(*La, 3, &e));
printf("刪除la表中的第一個數是%d\n", ListDelete_L(La, 1,&e));
printf("after delete first member ,la=");
PrintList_L(*La);
printf("create lb ,please enter 4 number:");
CreateList_L(Lb, 4);
printf("lb=");
PrintList_L(*Lb);
ListInsert_L(Lb, 2, 3);
printf("after insert 3, lb =");
PrintList_L(*Lb);
printf("MergeList function ,Lc=\n");
if(MergeList_L(La, Lb, Lc) ==OK)
{
printf("merget success\n");
PrintList_L(*Lc);
}
else
printf("merget failed");
return 0;
}
分別定義二級指針La,Lb,Lc，將它們作為參數傳遞到CreateList_L()函數中，這樣我們就可以在局部的函數裡面為
*La, *Lb, *Lc分配存儲空間，這些空間在結束函數調用時是不會消失的。C語言中參數傳遞都是值傳遞的方式：若以變量的值作為形參，傳入的是一份值的拷貝。函數無返回類型時，對變量值得改變僅在該調用函數內有效；若以指針或數組名坐形參，傳遞的是變量的地址，同樣的在調用函數內對這個地址的改變不會擴散到這個函數外，但對這個地址所代表的內存空間進行賦值，這種改變是永久的，結束調用時也不會被釋放。
在實現MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)時，一開始忘記為*Lc分配地址空間，使pc成為野指針，結果運行時程序一直掛掉浪費了好長一段時間。切記指針使用時一定要初始化。
運行結果：
