線性表—單連結清單的基本操作

1. 線性表的鍊式存儲又稱為單連結清單，對于每個連結清單結點，分為資料域data（存放元素的自身資訊）和指針域next（存放指向其後繼的指針）

//單連結清單結點類型的描述：
typedef struct LNode {
	ElemType data; //資料域
	struct LNode *next; //指針域
}LNode, *LinkList;
           

2.采用頭插法建立單連結清單

//從一個空表開始，生成新結點，并将讀取到的資料存放到新結點的資料域中，然後将新結點插入到連結清單的表頭
LinkList CreatListHead(LinkList &L) {
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode)); //建立頭結點
	L->data = NULL; //初始為空連結清單
	scanf("%d", &x); //輸入結點的值，c++為cin >> x;
	while (x != 9999) {
		s = (LNode*)malloc(sizeof(LNode)); //建立新的結點
		s->data = x; //将x存放在s的資料域中
		s->next = L->next;
		L->next = s; //将新結點插入表中，L為頭指針
		scanf("%d", &x);
	}
	return L;
}
           

3.采用尾插法建立單連結清單

LinkList CreatListTail(LinkList &L) {
	int x;
	L = (LinkList)malloc(sizeof(LNode)); //建立頭結點
	LNode *s, *r = L; //r為表尾指針
	scanf("%d", &x);
	while (x != 9999) {
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s; //将結點s插入到表尾
		r = s; //r指向新的表尾結點
		scanf("%d", x);
	}
	r->next = NULL; //尾結點指針為空
	return L;
}
           

4.按序号查找結點

//在單連結清單中從第一個結點出發，順指針next域逐個往下搜尋，直到找到第i個結點為止。
LNode *GetElem(LinkList L, int i) {
	int j = 1;
	LNode *p = L->next; //頭結點指針賦給p
	if (i == 0) return L; //若i=0， 則傳回頭結點
	if (i < 1) return NULL; //若i無效，則傳回NULL
	while (p && j < i) { //從第一個結點開始找，查找第i個結點
		p = p->next;
		j++;
	}
	return p; //傳回第i個結點的指針
}
           

5. 按值查找表結點

LNode *LocateElem(LinkList L, ElemType e) {
	LNode *p = L->next;
	while (p != NULL && p->data != e)
		p = p->next;
	return p;
}