數據結構C語言版-嚴蔚敏 筆記及課本程式碼（2）線性表的鏈式表示和實現

線性表的鏈式表示和實現

鏈表建立有兩種方式，一種爲頭插法建立，一種爲尾插法建立

1. 頭插法建立：從一個空表開始，重複讀入數據，生成新結點，
   將讀入數據存放入新結點的數據域中

2. 頭插法建立鏈表雖然演算法簡單，但生成的鏈表中結點的次序和輸入的順序相反，
   若希望二者的次序一致，可採用尾插法建表。該方法是將新結點插入到當前鏈表的表尾，
   使其成爲當前鏈表的尾結點。

頭插法建立鏈表

//頭插法建表
LNode *create_LinkList_L(){
	int data;
	LNode *head, *p; 
	head = (LNode *)malloc(sizeof(LNode));
	head -> next = NULL;
	while(TRUE){
		scanf("%d",&data);
		if (data == 32767) break;  //當輸入值爲32767時，退出 
		p = (LNode *)malloc(sizeof(LNode));  //建立新結點 
		p->data = data;  //給新結點數據域賦值 
		p->next = head->next;
		head->next = p;
	} 
	return (head);
 } 

尾插法建立鏈表

//尾插法建表
LNode *create_LinkList_R(){
	int data;
	LNode *head, *p ,*r;
	head = (LNode *)malloc(sizeof(LNode));
	head -> next = NULL;
	r = head;
	while(TRUE){
		scanf("%d",&data);
		if (data == 32767) break;
		p = (LNode *)malloc(sizeof(LNode));
		p -> data = data;
		
		p -> next = r -> next;
		r -> next = p;
		r = p;
	}
	return (head);
}

其餘操作：
ListInsert(LinkList &L,int index,ElemType e) ： 在帶頭結點的單鏈線性表L的第i個元素之前插入元素e
ListTravel(LinkList L) ：遍歷單鏈表

其他功能晚點放上來

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 
#define OVERFLOW -2
typedef int ElemType; 
typedef int Status;  

typedef struct LNode{ 
	ElemType data;  //數據域 
	struct LNode *next;
}LNode, *LinkList;


/* 
鏈表建立有兩種方式，一種爲頭插法建立，一種爲尾插法建立
1. 頭插法建立：從一個空表開始，重複讀入數據，生成新結點，
  將讀入數據存放入新結點的數據域中 
  
2. 頭插法建立鏈表雖然演算法簡單，但生成的鏈表中結點的次序和輸入的順序相反，
  若希望二者的次序一致，可採用尾插法建表。該方法是將新結點插入到當前鏈表的表尾，
  使其成爲當前鏈表的尾結點。 
*/

//頭插法建表
LNode *create_LinkList_L(){
	int data;
	LNode *head, *p; 
	head = (LNode *)malloc(sizeof(LNode));
	head -> next = NULL;
	printf("請輸入元素，按空格確認，輸入32767則退出輸入:\n");
	while(TRUE){
		scanf("%d",&data);
		if (data == 32767) break;  //當輸入值爲32767時，退出 
		p = (LNode *)malloc(sizeof(LNode));  //建立新結點 
		p->data = data;  //給新結點數據域賦值 
		p->next = head->next;
		head->next = p;
	} 
	return (head);
 } 
 
//尾插法建表
LNode *create_LinkList_R(){
	int data;
	LNode *head, *p ,*r;
	head = (LNode *)malloc(sizeof(LNode));
	head -> next = NULL;
	r = head;
	printf("請輸入元素，按空格確認，輸入32767則退出輸入:\n");
	while(TRUE){
		scanf("%d",&data);
		if (data == 32767) break;
		p = (LNode *)malloc(sizeof(LNode));
		p -> data = data;
		
		p -> next = r -> next;
		r -> next = p;
		r = p;
	}
	return (head);
}



Status GetElem(LinkList &L,int i, ElemType &e) {
  // L爲帶頭結點的單鏈表的頭指針。
  // 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR
  LinkList p;
  p = L->next;   
  int j = 1;           // 初始化，p指向第一個結點，j爲計數器
  while (p && j<i) {   // 順指針向後查詢，直到p指向第i個元素或p爲空
    p = p->next;  ++j;
  }
  if ( !p || j>i ) return ERROR;  // 第i個元素不存在
  e = p->data;   // 取第i個元素
  return OK;
} // GetElem_L


Status ListTravel(LinkList L){
	LinkList p=L->next; //跳過頭結點

	printf("當前單鏈表所有元素:");
	while(p != NULL)
	{
		printf("%d ,",p->data);
		p=p->next;
	}
	printf("\n");
}

Status ListInsert(LinkList &L,int index,ElemType e){
	// 在帶頭結點的單鏈線性表L的第i個元素之前插入元素e
	int i = 0;
	LinkList in, p = L;  //p指向頭結點
	while(p && i < index - 1){  // 尋找 i 的前一個元素 
		p = p -> next;
		i++;
	}
	if (!p)
		return ERROR; 
	in = (LNode *)malloc(sizeof(LNode)); //生成新結點 
	in -> data = e;
	in -> next = p -> next;
	p -> next = in;
	return OK; 
	
}

int main(){
	int e;
	LinkList L = create_LinkList_L(); //以頭結點，用頭插法建表 
	ListTravel(L);
	
	printf("==========獲取第i個元素=========\n");
	GetElem(L,2,e);
	printf("%d\n",e);
	
	printf("==========ListInsert=========\n");
	int flag;
	flag = ListInsert(L,6,10);
	if (flag) ListTravel(L); else printf("沒有該位置"); 


}