c語言鏈表實現
⑴ c語言！！！程序設計:建立一個學生信息鏈表,包括學號,姓名,成績.(實現添加,刪除,查詢,排序,平均)
代碼如下：
/*用c語言鏈表編寫一個學生信息系統程序，要求輸出學生的學號，姓名，性別，學號，姓名，成績(實現添加，刪除，查詢,排序，平均)*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int n=5;
/*
* nodeEntry : 節點數據類型
* nodeADT : 節點結構
* linkADT : 鏈表結構
*/
typedef struct Student
{
int num;
char name[30];
char sex;
float score1;//語文
float score2;//數學
float score3;//英語
//struct Student *next;
}Student;
typedef struct linkCDT {
nodeADT head;
}*linkADT;
/*
* InitLink : 初始化鏈表
* CreateNode : 創建節點
* AppendLink : 添加數據
*/
nodeADT CreateNode(Student entry) {
nodeADT p=(nodeADT)malloc(sizeof*p);
p->entry=entry,p->next=0;
return p;
}
/*
SortLink : 排序鏈表
//按學號排序
void SortLinkID(linkADT link) {
nodeADT pHead,pRear,p,tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->entry.num>=p->entry.num)
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
//按英語成績排序
void SortLinkEnglish(linkADT link) {
nodeADT pHead,pRear,p,tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->entry.score3>=p->entry.score3)
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
}
//按姓名的字典序進行排序
void SortLinkName(linkADT link) {
nodeADT pHead,pRear,p,tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->entry.name[0]>=p->entry.name[0])
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
}
//按姓名的長度進行排序
void SortLinkNameLength(linkADT link) {
nodeADT pHead,pRear,p,tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (strlen(pHead->entry.name)>=strlen(p->entry.name))
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
循環鏈表是與單鏈表一樣
是一種鏈式的存儲結構，所不同的是，循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。
循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點：
1、在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種情況還使用於在最後一個結點後插入一個新的結點。
2、在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。
以上內容參考：網路-鏈表
⑵ 編寫一個C語言程序 實現單鏈表的基本操作
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct Node
{
int data;
struct Node * pNext;
} * PNODE, NODE;
PNODE establish_list (void);
void traverse_list (PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
void sort_list(PNODE pHead);
void insert_list(PNODE pHead, int pos, int val);
int delete_list(PNODE pHead, int pos, int val);
void freeer(PNODE pHead);
int main(void)
{
PNODE pHead;
int len, i, j, val;
pHead = establish_list();
traverse_list(pHead);
if(is_empty(pHead))
printf("鏈表為空\n");
else
printf("鏈表不空\n");
len = length_list(pHead);
printf("鏈表的長度為: %d\n", len);
sort_list(pHead);
traverse_list(pHead);
printf("請輸入您要在第幾個節點插入\n");
scanf("%d", &i);
printf("請輸入您要在第%d個節點插入的值\n", i);
scanf("%d", &j);
insert_list(pHead, i, j);
traverse_list(pHead);
printf("請輸入您要第幾個刪除的節點\n");
scanf("%d", &i);
val = delete_list(pHead, i, val);
printf("您刪除的節點值為: %d\n", val);
traverse_list(pHead);
freeer(pHead);
return 0;
}
PNODE establish_list(void)//初始化鏈表，返回頭結點地址
{
int val, len;
PNODE Tem;
PNODE pNew;
PNODE pHead;
pHead = (PNODE)malloc(sizeof(NODE));
Tem = pHead;
if(NULL == pHead)
{
printf("分配失敗");
exit(-1);
}
Tem->pNext = NULL;
printf("請輸入您要定義節點的長度: ");
scanf("%d", &len);
for (int i=0;i<len;++i)
{
printf("請輸入第%d個節點的值: ", i+1);
scanf("%d", &val);
pNew = (PNODE)malloc(sizeof(NODE));
if(NULL == pNew)
{
printf("分配失敗");
exit(-1);
}
pNew->data = val;//首先把本次創建的新節點的值付給新節點的數據域
Tem->pNext = pNew;//然後使用臨時的節點變數的指針域保存了新節點的地址，也就是指向了新節點
pNew->pNext = NULL;//如何再不循環，新節點成為最後一個節點
Tem = pNew;//把本次分配的新節點完全的賦給Tem，Tem就成為了這次新節點的影子,那麼下次分配新節點時可以使用上個新節點的數據
}
return pHead;
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead;//使用P是為了不改寫頭結點里保存的地址
p = pHead->pNext;//使P指向首節點
while(p != NULL)//P本來就是頭結點的指針域，也就是首節點的地址，既然是地址就可以直接判斷p是否等於NULL
{
printf("%d ", p->data);
p = p->pNext;//使P每循環一次就變成P的下一個節點
}
}
bool is_empty(PNODE pHead)
{
if(NULL == pHead->pNext)
return true;
else
return false;
}
int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int len = 0;
while(p != NULL)
{
len++;
p = p->pNext;
}
return len;
}
void sort_list(PNODE pHead)
{
int i, j, t, len;
PNODE p, q;
len = length_list(pHead);
for(i=0,p=pHead->pNext;i<len;i++,p=p->pNext)//逗號後只是為了找到下一個節點，因為不是數組，所以不能使用下標來++
{
for(j=0,q=pHead->pNext;j<len;j++,q=q->pNext)
if(q->data > p->data)//這里的大小與號可以決定是升序還是降序，如果是大於號就是升序,反之小於號就是降序
{
t = q->data;
q->data = p->data;
p->data = t;
}
}
return;
}
void insert_list(PNODE pHead, int pos, int val)
{
int i;
PNODE q = pHead;
PNODE p = pHead;
if(pos > 0 && pos <= length_list(pHead))
{
for(i=0;i<pos;i++)
{
q = q->pNext;//q就是要插入的連接點
}
for(i=1;i<pos;i++)
{
p = p->pNext;//p就是要插入連接點的前一個節點
}
PNODE pNew = (PNODE)malloc(sizeof(NODE));
p->pNext = pNew;
pNew->data = val;
pNew->pNext = q;
}
else if(pos > length_list(pHead))//追加
{
PNODE t;
t = pHead;
PNODE PN;
PN = (PNODE)malloc(sizeof(NODE));
if(PN == NULL)
printf("分配失敗");
else
while(t->pNext != NULL)
{
t = t->pNext;//使T->pNext成為尾結點
}
PN->data = val;//給新節點賦予有效數據
t->pNext = PN;//使尾結點的指針域指向了新的結點
PN->pNext = NULL;//新節點成為尾結點
}
else
printf("error\n");
return;
}
int delete_list(PNODE pHead, int pos, int val)
{
int i, j;
PNODE q, p;
q = pHead;
p = pHead;
if(pos > 0 && pos <= length_list(pHead))//保證刪除的是節點的有效數
{
for(i=0;i<pos;i++)
{
p = p->pNext;
}
for(j=1;j<pos;j++)
{
if(pos == 0)
q = pHead;
else
q = q->pNext;
}
q->pNext = p->pNext;
val = p->data;
free(p);
return val;
}
else
printf("error");
}
void freeer(PNODE pHead)
{
PNODE pT = pHead;
while(NULL != pHead->pNext)
{
free(pT);
pT = pT->pNext;
}
return;
}
/*
好久以前寫的一個鏈表了，有排序，插入，刪除，輸出，判斷是否為空，甚至還有釋放堆中內存的功能
*/