關于C語言的指針、鏈表的原理和各類操作

  今天課上我們老師為我們講述了c語言的指針、鏈表的原理以及各類操作。

一、指針

1、指針

  指針是一個存儲計算機內存地址的變量。從指針指向的內存讀取數據稱作指針的取值。指針可以指向某些具體類型的變量地址，例如int、long和double。指針也可以是void類型、NULL指針和未初始化指針。指針是一個存儲計算機內存地址的變量。從指針指向的內存讀取數據稱作指針的取值。指針可以指向某些具體類型的變量地址，例如int、long和double。指針也可以是void類型、NULL指針和未初始化指針。

2、數組

  C語言的數組表示一段連續的內存空間，用來存儲多個特定類型的對象。數組和指針不是同一種結構因此不可以互相轉換。而數組變量指向了數組的第一個元素的內存地址。

3、指針與結構體

  就像數組一樣，指向結構體的指針存儲了結構體第一個元素的內存地址。與數組指針一樣，結構體的指針必須聲明和結構體類型保持一致，或者聲明為void類型。

我們在使用c語言進行編寫程序的時候，就一定會使用上指針，指針的操作是編寫程序的一個點。如何更好的使用指針，將是我們進行更好的書寫程序的關鍵。我認為弄清楚下面幾個要點，可以更好的理解指針：

1：指針是一個地址，指向的是個類型

2：指針指向的是地址，地址指向的是內容

3：指針的指針，是面對于指針的變量

二、鏈表

      鏈表我的理解要包含以下特征：（1）.由n個節點離散分配；（2）.每個節點通過指針連接（3）每一個節點由一個前驅節點和一個后驅節點（4）.首節點沒有前驅節點，尾節點沒有后驅節點；

     滿足上面的4條，我們就稱為鏈表；鏈表既然由很多個節點，那節點又由什么組成？節點由兩個部分組成，一是數據域，用來存放有效數據；二是指針域，用來指向下一個節點；下面用C語言來構建鏈表數據結構，首先應該構造出節點，然后再把所有的節點連起來，就構成了鏈表；

我認為學生宿舍的管理系統中，指針的作用就是使其保存到下一個地址

下面是單鏈表的學生信息管理系統

#include "string.h"  

#include "sys/malloc.h"  

#include "stdlib.h"  

#include "stdio.h"  

#include "time.h"  

#include "sys/types.h"  

#define MAXSIZE 100  

typedef struct Student  

{  

    char sname[9];  

    char sno[5];  

    int score;  

}DataType;  

typedef struct  

{  

    DataType data;  

    struct Node *next;  

}LinkList;  

LinkList * inputdata();  

void display(LinkList * p);  

//遍歷鏈表  

void displayAll(LinkList * L);  

//插入  

LinkList * createTailList();//尾插  

LinkList * createHeadList();//頭插  

//查詢  

void getElem(LinkList * L, int i);//按序號  

void locateElemBysno(LinkList * L, char ch[]);//按值  

void locateElemBysname(LinkList * L, char ch[]);  

int lengthList(LinkList * L);  

//插入  

void insertElem(LinkList * L, int i);//在第i個結點前進行插入  

void insertElemBysno(LinkList * L, char ch[5]);//按學號  

void deleteElem(LinkList * L, char ch[]);  

//排序  

void insertSort(LinkList * L);  

int menue();  

int main(int argc,char *argv[])  

{  

    LinkList *L;  

    char sno[5] = {'\0'};  

    char sname[9] = {'\0'};  

    int b = 1;  

    int i = 1;  

    while (b) {  

        switch(menue())  

        {  

            case 1:  

                L = createTailList();  

                //L = createHeadList();  

                break;  

            case 2:  

                //displayAll(L);  

                printf("\t◎輸入插入哪個位置前：");  

                scanf("%d", &i);  

                insertElem(L, i);  

                //scanf("%s", sno);  

                //insertElemBysno(L, sno);  

                break;  

            case 3:  

                printf("\t◎輸入待刪除學生的學號：");  

                scanf("%s", sno);  

                deleteElem(L, sno);  

                break;  

            case 4:  

                printf("╭═══════════════════════════════╮\n");  

                printf("║\t學生總數為：%d\t\t║\n", lengthList(L));  

                printf("╰═══════════════════════════════╯\n\n");  

                break;  

            case 5:  

                printf("\t◎輸入待查找學生的學號：");  

                scanf("%s", sno);  

                locateElemBysno(L, sno);  

                break;  

            case 6:  

                printf("\t◎輸入待查學生的位置：");  

                scanf("%d", &i);  

                getElem(L, i);  

                break;  

            case 7:  

                displayAll(L);  

                break;  

            case 8:  

                insertSort(L);  

                break;  

            case 9:  

                i = 2;  

                while (i)  

                {                      

                    system("clear");  

                    printf("\033[5m");  

                    printf("\033[?25l");        //隱藏光標  

                    printf("\n\n\n\n\n\n");  

                    printf("╭═══════════════════════════════╮\n");  

                    printf("║\t正在退出(%d秒)\t\t║\n", i--);  

                    printf("╰═══════════════════════════════╯\n");  

                    sleep(1);  

                }  

                printf("\033[0m");  

                system("clear");  

                return 0;  

                break;  

            default:  

                i = 2;  

                while (i)  

                {  

                    system("clear");  

                    printf("╭═══════════════════════════════╮\n");  

                    printf("║操作數無效，正在返回主菜單(%d秒)║\n", i--);  

                    printf("╰═══════════════════════════════╯\n");  

                    sleep(1);  

                }  

                continue;  

        }  

        getchar();  

        printf("PRESS ENTER TO CONTINUE!");  

        while (1) {  

            if ('\n' == getchar())  

            {  

                break;  

            }  

        }  

    }  

    return 0;  

}  

int menue()  

{  

    system("clear");  

    //警告音  

    printf("\033[0m");              //關閉所有屬性  

    printf("\033[44;37m");          //47是字背景顏色,33是字體的顏色  

    printf ("\033[5m");             //閃爍  

    printf("\n^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^\n\n");  

    printf("\033[0m");              //關閉所有屬性  

    printf("\033[44;37m");  

    printf("╭═══════════════════════════════╮\n");  

    printf("║\t學生成績管理程序\t║\n");  

    printf("║\t\t\t\t║\n");  

    printf("║\t<1>創建\t\t\t║\n");  

    printf("║\t<2>指定位置后插入\t║\n");  

    printf("║\t<3>按位置刪除\t\t║\n");  

    printf("║\t<4>求學生總數\t\t║\n");  

    printf("║\t<5>按學號查找\t\t║\n");  

    printf("║\t<6>按位置查找\t\t║\n");  

    printf("║\t<7>顯示所有學生\t\t║\n");  

    printf("║\t<8>成績排序\t\t║\n");  

    printf("║\t<9>退出\t\t\t║\n");  

    printf("╰═══════════════════════════════╯\n\n");  

    printf ("\033[5m");  

    printf("^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^ ^_^\n\n");  

    printf("\033[0m");              //關閉所有屬性  

    time_t rawtime;  

    struct tm * timeinfo;  

    time ( &rawtime );  

    timeinfo = localtime ( &rawtime );  

    //printf ( "\t\007%s", asctime (timeinfo) );  

    printf ("\033[;34m");  

    printf ("\t[%4d-%02d-%02d %02d:%02d:%02d]\n",  

            1900+timeinfo->tm_year,  

            1+timeinfo->tm_mon,  

            timeinfo->tm_mday,  

            timeinfo->tm_hour,  

            timeinfo->tm_min,  

            timeinfo->tm_sec);  

    char colorname[3][20] = {{"RED"}, {"BLUE"}, {"YELLLOW"}};  

    srand(time(&rawtime));  //時間觸發  

    //textcolor(colorname[rand()%3]);  

    //printf("\t[textcolor is %s]\n", colorname[rand()%3]);  

    //顏色碼和控制碼 我的參考鏈接 http://wenku.baidu.com/view/a38f77ff910ef12d2af9e70b.html  

    printf("\t◎輸入功能項：");      

    int a = 0;  

    scanf("%d",&a);  

    printf("\033[0m");  

    system("clear");  

    return a;  

}  

LinkList * inputdata()  

{  

    LinkList *s = NULL;  

    char sno[5] = {'\0'};  

    char sname[9] = {'\0'};  

    int  score = 0;  

    printf("\tsno\t->");  

    scanf("%s", sno);  

    if (sno[0] == '#') {  

        return s;  

    }  

    s = (LinkList *)malloc(sizeof(LinkList));  

    strcpy(s -> data.sno, sno);  

    printf("\tsname\t->");  

    scanf("%s", sname);  

    strcpy(s -> data.sname, sname);  

    printf("\tscore\t->");  

    scanf("%d", &score);  

    s -> data.score = score;  

    printf("\n");  

    return s;  

}  

void display(LinkList * p)   

{  

    printf("╭═══════════════════════════════════════════════╮\n");  

    printf("║\tsno\t\tsname\t\tscore\t║\n");  

    printf("║\t%s\t\t%s\t\t%-4d\t║\n", p->data.sno, p->data.sname, p->data.score);  

    printf("╰═══════════════════════════════════════════════╯\n\n");}  

void displayAll(LinkList * L)  

{  

    printf("╭═══════════════════════════════════════════════╮\n");  

    printf("║\tsno\t\tsname\t\tscore\t║\n");  

    LinkList * p = L -> next;  

    while(p)  

    {  

        printf("║\t%s\t\t%s\t\t%-4d\t║\n", p->data.sno, p->data.sname, p->data.score);  

        p = p -> next;  

    }  

    printf("╰═══════════════════════════════════════════════╯\n\n");  

}  

LinkList * createTailList()  

{  

    //鏈表頭結點  

    LinkList * L = (LinkList *)malloc(sizeof(LinkList));  

    //結點  

    LinkList * s = NULL;  

    //尾結點  

    LinkList * r = L;  

    printf("╭═══════════════════════════════════════════════╮\n");  

    printf("║\t\t尾插法建立\t\t\t║\n");  

    printf("║\t請輸入學生信息（當學號為\"#\"時結束）\t║\n");  

    printf("║\t\t\t\t\t\t║\n");  

    printf("║\t學號sno     （不超過4位）\t\t║\n");  

    printf("║\t姓名sname   （不超過4個漢字）\t\t║\n");  

    printf("║\t成績score   （int型）\t\t\t║\n");  

    printf("╰═══════════════════════════════════════════════╯\n\n");  

    while (1) {  

        s = inputdata();  

        if (!s) {  

            break;  

        }  

        r->next = s;  

        r = s;  

    }  

    r->next = NULL;  

    return L;  

}  

LinkList * createHeadList()  

{  

    //鏈表頭結點  

    LinkList * L = (LinkList *)malloc(sizeof(LinkList));  

    //結點  

    LinkList * s = NULL;  

    printf("╭═══════════════════════════════════════════════╮\n");  

    printf("║\t\t頭插法建立\t\t║\n");  

    printf("║\t請輸入學生信息（當學號為\"#\"時結束）\t║\n");  

    printf("║\t\t\t\t\t\t║\n");  

    printf("║\t學號sno     （不超過4位）\t\t║\n");  

    printf("║\t姓名sname   （不超過4個漢字）\t\t║\n");  

    printf("║\t成績score   （int型）\t\t\t║\n");  

    printf("╰═══════════════════════════════════════════════╯\n\n");  

    while (1) {  

        s = inputdata();  

        if (!s) {  

            break;  

        }  

        s->next = L->next;  

        L->next = s;  

    }  

    return L;  

}  

void getElem(LinkList * L, int i)  

{  

    LinkList * p = L;  

    int j = 0;  

    while (p && j<i) {  

        p = p->next;  

        j++;  

    }  

    if (!p) {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    else  

    {  

        display(p);  

    }  

}  

void locateElemBysno(LinkList * L, char ch[5])  

{  

    LinkList * p = L->next;  

    while (p && (0 != strcmp(p->data.sno, ch)))  

    {  

        p = p -> next;  

    }  

    if (!p) {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    else  

    {  

        display(p);  

    }  

}  

void locateElemBysname(LinkList * L, char ch[9])  

{  

    LinkList * p = L->next;  

    while (p && (0 != strcmp(p->data.sname, ch)))  

    {  

        p = p -> next;  

    }  

    if (!p) {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    else  

    {  

        display(p);  

    }  

}  

int lengthList(LinkList * L)  

{  

    LinkList * p = L->next;  

    int j = 0;  

    while (p) {  

        p = p->next;  

        j ++;  

    }  

    return j;  

}  

void insertElem(LinkList * L, int i)  

{  

    LinkList * s = inputdata();  

    LinkList * p = L;  

    int j = 0;  

    while (p && j<i-1)  

    {  

        p = p->next;  

        j++;  

    }  

    if (p && p->next)  

    {  

        s->next = p->next;  

        p->next = s;  

    }  

    else  

    {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    displayAll(L);  

}  

void insertElemBysno(LinkList * L, char ch[5])  

{  

    LinkList * p = L;  

    LinkList * s = NULL;  

    while (p && (0 != strcmp(p->data.sno, ch)))  

    {  

        p = p->next;  

    }  

    if (!p) {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    else  

    {  

        s = inputdata();  

        s->next = p->next;  

        p->next = s;  

    }  

}  

void deleteElem(LinkList * L, char ch[5])  

{  

    LinkList *p, *q;  

    p = L->next;  

    q=L;  

    while (p && (strcmp(p->data.sno, ch) != 0)) {  

        q = p;  

        p = p->next;  

    }  

    if (!p) {  

        printf("╭═══════════════════════════════╮\n");  

        printf("║\tDon't find the student!\t║\n");  

        printf("╰═══════════════════════════════╯\n\n");  

    }  

    else  

    {  

        display(p);  

        q->next = p->next;  

        free(p);  

    }  

}  

void insertSort(LinkList * L)  

{  

    LinkList * L1;  

    LinkList * p;  

    LinkList * q;  

    LinkList * s;  

    int len;  

    len = lengthList(L);  

    L1 = (LinkList *)malloc(sizeof(LinkList));  

    if (L->next) {  

        s = (LinkList *)malloc(sizeof(LinkList));  

        strcpy(s->data.sno, L->data.sno);  

        strcpy(s->data.sname, L->data.sname);  

        s->data.score = L->data.score;  

        s->next = NULL;  

        L1->next = s;  

        q = L->next;  

    }  

    else  

    {  

        printf("╭═══════════════════════════════════╮\n");  

        printf("║\tThe student link list is empty!\n║\n");  

        printf("╰═══════════════════════════════════╯\n\n");  

        return;  

    }  

    while (q) {  

        p = L1->next;  

        while (p &&(p->data.score >= q->data.score))  

        {  

            p = p->next;  

        }  

        s = (LinkList *)malloc(sizeof(LinkList));  

        strcpy(s->data.sno, q->data.sno);  

        strcpy(s->data.sname, q->data.sname);  

        s->data.score = q->data.score;  

        if (!p) {  

            s->next = NULL;  

            p->next = s;  

        }  

        else  

        {  

            s->next = p->next;  

            p->next = s;  

        }  

        q = q->next;  

    }  

    displayAll(L1);  

}