〇、寫在前面

小伙伴們要多多體會(huì)，不要全部借鑒哦！文章來源地址http://www.zghlxwxcb.cn/news/detail-719951.html

一、順序表的初始化、查找、插入、刪除、輸出、撤銷

/*
_* _ coding : utf - 8 _ * _

Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/

#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;



// 1、參照課本程序2.1～2.7，編寫程序，完成順序表的初始化、查找、插入、刪除、輸出、撤銷等操作。

typedef struct {
	int n;               //順序表的長度
	int maxLength;       //順序表的最大長度
	ElemType* element;   //存放動(dòng)態(tài)分配一維數(shù)組首地址
}SeqList;


//順序表初始化

Status Init(SeqList* L, int mSize) {
	
	L->maxLength = mSize;		// 容量設(shè)為mSize

	L->n = 0;					// 大小設(shè)為0

	L->element = (ElemType*)malloc(sizeof(ElemType) * mSize);	// 申請(qǐng)容量大小的動(dòng)態(tài)空間

	if (L->element)			// 如果申請(qǐng)成功，返回OK
		return OK;
	exit(0);				// 申請(qǐng)不成功，退出
}


//順序表的查找
Status Find(SeqList seqList, int i, ElemType* x) {
	if (i < 0 || i > seqList.n - 1) {
		return ERROR;    //判斷元素下標(biāo)i是否越界
	}
	*x = seqList.element[i];     //取出element[i]的值通過參數(shù)x返回
	return OK;
}

//初始化插入
Status Insert(SeqList* seqList, int i, ElemType x) {
	int j;
	if (i<-1 || i>seqList->n - 1)                      //判斷下標(biāo)i是否越界
		return ERROR;
	if (seqList->n == seqList->maxLength)                    //判斷順序表存儲(chǔ)空間是否已滿
		return ERROR;
	for (j = seqList->n - 1; j > i; j--) {
		seqList->element[j + 1] = seqList->element[j];   //從后往前逐個(gè)后移元素
	}
	seqList->element[i + 1] = x;                       //將新元素放入下標(biāo)為i+1的位置
	seqList->n++;                           //長度+1
	return OK;
}


//順序表的刪除
Status Delete(SeqList* seqList, int i) {
	int j;
	if (i<0 || i>seqList->n - 1) {                   //下標(biāo)i是否越界
		return ERROR;
	}
	if (!seqList->n) {                           //順序表是否為空
		return ERROR;
	}
	for (j = i + 1; j < seqList->n; j++) {
		seqList->element[j - 1] = seqList->element[j];   //從前往后逐個(gè)前移元素
	}
	seqList->n--;                              //表長減1
	return OK;
}


//順序表輸出
int Output(SeqList seqList) {
	int i;
	if (!seqList.n)
		return ERROR;                 //判斷順序表是否為空
	for (i = 0; i <= seqList.n - 1; i++)
		printf("%d ", seqList.element[i]);  //從前往后逐個(gè)輸出元素
	return OK;
}



// 順序表的撤銷
void Destroy(SeqList* L) {
	(*L).n = 0;
	(*L).maxLength = 0;
	free((*L).element);
}



int main()
{
	int i, findResult;
	SeqList list;
	Init(&list, 10);
	                   //對(duì)線性表初始化，初始化容量為10
	for (i = 0; i < 10; i++) {
		Insert(&list, i - 1, i);			//將0-8插入到順序表中
	}
	printf("插入0~10后，表為：\n");
	Output(list);
	printf("\n");
	Delete(&list, 0);                       //刪除0
	printf("刪除下表為0處的元素后，表為：\n");
	Output(list);
	Find(list, 2, &findResult);				//查找下標(biāo)為2的元素并輸出
	printf("\n下表為2處的元素值為:");
	printf("%d", findResult);
	Destroy(&list);
	return 0;
}



/*

1、數(shù)據(jù)結(jié)構(gòu)：
順序表SeqList的數(shù)據(jù)結(jié)構(gòu)為C語言結(jié)構(gòu)體, 
內(nèi)含三個(gè)數(shù)據(jù)成員n(線性表的實(shí)際大小), maxLength(線性表的存儲(chǔ)容量), element(線性表存儲(chǔ)元素的首地址)



核心算法:

1、首先創(chuàng)建一個(gè)線性表結(jié)構(gòu)體變量SeqList list; 調(diào)用Init(SeqList* L, int mSize)對(duì)線性表進(jìn)行存儲(chǔ)容量的設(shè)置和
存儲(chǔ)空間內(nèi)存的申請(qǐng)。
2、插入算法：調(diào)用 Insert(SeqList* seqList, int i, ElemType x), 將傳入的元素的值 x 放到 順序表第 i+1 個(gè)位置上。
首先從線性表的最后一個(gè)元素開始從后往前逐個(gè)后移元素，直到將第i+1個(gè)元素移動(dòng)到第i+2個(gè)位置，然后將要插入的元素插入到線性表的
第i+1個(gè)位置上。
3、刪除算法：	調(diào)用 Delete(SeqList* seqList, int i), 傳入坐標(biāo)處的元素刪除。
首先從線性表的第i+1的未知開始, 依次將元素前移。
 

 Status Init(SeqList* L, int mSize);
 Status Find(SeqList seqList, int i, ElemType* x);
 Status Insert(SeqList* seqList, int i, ElemType x);
 int Output(SeqList seqList);
 void Destroy(SeqList* L);


*/

二、帶表頭結(jié)點(diǎn)單鏈表的初始化、查找、插入、刪除、輸出、撤銷

/*
_* _ coding : utf - 8 _ * _

Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/


#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;

//2、已知帶表頭結(jié)點(diǎn)單鏈表的類型定義如下：	 
//參照課本程序2.8～2.14，編寫程序，完成帶表頭結(jié)點(diǎn)單鏈表的初始化、查找、插入、刪除、輸出、撤銷等操作。

typedef struct Node {
    ElemType element;     //結(jié)點(diǎn)的數(shù)據(jù)域
    struct Node* link;   //結(jié)點(diǎn)的指針域
}Node;

typedef struct {
    struct Node* head;    //表頭結(jié)點(diǎn)
    int n;
}ListHeader;


Status Init(ListHeader* h);
Status Find(ListHeader* h, int i, ElemType* x);
Status Insert(ListHeader* h, int i, ElemType x);
Status Delete(ListHeader* h, int i);
Status Output(ListHeader* h);
void Destroy(ListHeader* h);


//帶表頭結(jié)點(diǎn)單鏈表的初始化
Status Init(ListHeader* h) {
    h->head = (Node*)malloc(sizeof(Node));      //生成表頭結(jié)點(diǎn)
    if (!h->head) {
        return ERROR;
    }
    h->head->link = NULL;                     //設(shè)置單鏈表為空表
    h->n = 0;
    return OK;
}


//帶表頭結(jié)點(diǎn)單鏈表的查找
Status Find(ListHeader* h, int i, ElemType* x) {
    Node* p;
    int j;
    if (i < 0 || i > h->n - 1) {
        return ERROR;
    }
    p = h->head->link;
    for (j = 0; j < i; j++) {
        p = p->link;
    }
    *x = p->element;
    return OK;
}


//帶表頭結(jié)點(diǎn)單鏈表的插入
Status Insert(ListHeader* h, int i, ElemType x) {
    Node* p, * q;
    int j;
    if (i<-1 || i>h->n - 1)
        return ERROR;
    p = h->head;                      //從頭結(jié)點(diǎn)開始找ai元素所在的結(jié)點(diǎn)p
    for (j = 0; j <= i; j++) {
        p = p->link;
    }
    q = (Node*)malloc(sizeof(Node));  //生成新結(jié)點(diǎn)q
    q->element = x;
    // 將 q 插在 p 和 p->link 之間
    q->link = p->link;                //新結(jié)點(diǎn)q插在p之后
    p->link = q;
    h->n++;
    return OK;
}


//帶表頭結(jié)點(diǎn)單鏈表的刪除
Status Delete(ListHeader* h, int i) {
    int j;
    Node* p, * q;
    if (!h->n) {
        return ERROR;
        if (i<0 || i>h->n - 1) {
            return ERROR;
        }
    }
    q = h->head;
    for (j = 0; j < i; j++) {
        q = q->link;
    }
    p = q->link;
    // 將 q->link 改為 q->link->link;  即q的下一個(gè)節(jié)點(diǎn)的下一個(gè)，再將q的下一個(gè)節(jié)點(diǎn)刪除
    q->link = q->link->link;            
    free(p);                       
    h->n--;
    return OK;
}


//帶表頭結(jié)點(diǎn)單鏈表的輸出
Status Output(ListHeader* h) {
    Node* p;
    if (!h->n)
        return ERROR;
    p = h->head->link;
    printf("the linklist is:");
    while (p) {
        printf("%d ", p->element);
        p = p->link;
    }
    printf("\n");
    return OK;
}


//帶表頭結(jié)點(diǎn)單鏈表的撤銷
void Destroy(ListHeader* h) {
    Node* p, * q;
    while (h->head->link) {
        q = h->head->link;
        p = h->head->link->link;
        free(h->head->link);
        h->head = q;
    }
}



int main()
{
    int i, x;
    ListHeader list;
    Init(&list);
    for (i = 0; i < 9; i++) {
        Insert(&list, i - 1, i);    //插入0~8
    }
    printf("插入0~8，表為：\n");
    Output(&list);
    printf("\n");
    Delete(&list, 0);                //刪除0
    printf("刪除下標(biāo)為0處的元素，表為：\n");
    Output(&list);
    printf("\n");

    Delete(&list, 0);                //刪除0
    printf("刪除下標(biāo)為0處的元素，表為：\n");
    Output(&list);
    printf("\n");

    Find(&list, 0, &x);               //查找下標(biāo)為0的元素
    printf("查找下標(biāo)為0的元素值為：\n");
    printf("%d ", x);
    printf("\n");

    Destroy(&list);
    printf("\n\n\n");
    return 0;
}

/*
   參照課本程序2.8～2.14，編寫程序，完成帶表頭結(jié)點(diǎn)單鏈表的初始化、查找、插入、刪除、輸出、撤銷等操作。
    1、初始化：先為表頭節(jié)點(diǎn)申請(qǐng)一個(gè)節(jié)點(diǎn)的空間，
*/

三、多項(xiàng)式

/*
_* _ coding : utf - 8 _ * _

Time : 2022/9/4 21 : 15
Author : Yan Fanyu
Version : V 0.1
File : main.cpp
Describe : Github link : https://github.com/YanFanYu2001
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct PNode {
    int coef;             //系數(shù)
    int exp;              //指數(shù)
    struct PNode* link;
}PNode;

typedef struct {
    struct PNode* head;
}Polynominal;


//多項(xiàng)式的創(chuàng)建
void Create(Polynominal* p) {
    PNode* pn, * pre, * q;
    p->head = (PNode*)malloc(sizeof(PNode));
    p->head->exp = -1;
    p->head->link = p->head;               //對(duì)教材做了修改
    //p->head->link = NULL;                //教材原代碼
    printf("請(qǐng)輸入表達(dá)式的項(xiàng)數(shù)\n");
    int nn = 0;
    scanf_s("%d", &nn);
    for (int i = 0; i < nn; i++)
    {
        pn = (PNode*)malloc(sizeof(PNode));
        printf("\n請(qǐng)輸入系數(shù):\n");
        scanf_s("%d", &pn->coef);
        printf("請(qǐng)輸入階數(shù):\n");
        scanf_s("%d", &pn->exp);
        if (pn->exp == -1) break;
        pre = p->head;
        q = p->head->link;
        while (q && q->exp > pn->exp) {
            pre = q;
            q = q->link;
        }
        pn->link = q;
        pre->link = pn;
    }
}


//多項(xiàng)式輸出
void Output(Polynominal p) {
    printf("expression = ");
    PNode* q;
    int flag = 1;                                   //打標(biāo)記,記錄是否為第一項(xiàng)
    q = p.head->link;
    if (!q) {
        return;
    }
    while (q != p.head) {
        if (!flag && (q->coef > 0)) printf("+");    //在非第一項(xiàng)的正系數(shù)前輸出+號(hào)
        flag = 0;                                   //flag置為0,表示不是第一項(xiàng)
        if (q->coef == 0) {                           //當(dāng)前項(xiàng)系數(shù)為0
            return;
        }
        if (q->coef != 1) {       //當(dāng)前項(xiàng)系數(shù)不為0&&不為1
            printf("%d", q->coef);
        }
                       
        switch (q->exp) {                             //判斷當(dāng)前項(xiàng)指數(shù)
        case 0:break;                           //當(dāng)前項(xiàng)指數(shù)為0,退出
        case 1:printf("X"); break;               //當(dāng)前項(xiàng)指數(shù)為1,輸出X
        default:printf("X^%d", q->exp); break;    //當(dāng)前項(xiàng)指數(shù)不為0,也不為1
        }
        q = q->link;
    }
    printf("\n");
}


//多項(xiàng)式的相加,結(jié)果存入qx中
void Add(Polynominal* px, Polynominal* qx) {
    PNode* q, * q1 = qx->head, * p, * p1, * temp;    //q1指向qx的表頭結(jié)點(diǎn)
    p = px->head->link;                       //p指向多項(xiàng)式px的第一個(gè)結(jié)點(diǎn)
    p1 = px->head;
    q = q1->link;                             //q1是q的前驅(qū)
    while (p->exp >= 0) {
        while (p->exp < q->exp) {               //跳過q->exp大的項(xiàng)
            q1 = q;
            q = q->link;
        }
        // 如果兩多項(xiàng)式的階數(shù)相等，則對(duì)應(yīng)系數(shù)相加，結(jié)果存放在qx中
        if (p->exp == q->exp) {                
            q->coef = q->coef + p->coef;
            // 如果相加后系數(shù)為0
            if (q->coef == 0) {                 
                q1->link = q->link;           //刪除q
                free(q);                      //釋放q的空間
                q = (PNode*)malloc(sizeof(PNode));
                q = q1->link;                 //重置q指針
                p = p->link;
            }
            else {                             //若相加后系數(shù)不為0
                q1 = q;                       //q1后移
                q = q->link;
                p = p->link;                  //p也后移
            }
        }
        else {                                 //p->exp > q->exp的情況
            temp = (PNode*)malloc(sizeof(PNode));     //以p的系數(shù)和指數(shù)生成新結(jié)點(diǎn)
            temp->coef = p->coef;
            temp->exp = p->exp;
            temp->link = q1->link;
            q1->link = temp;
            q1 = q1->link;
            p = p->link;
        }
    }
}


// 多項(xiàng)式乘法 (結(jié)果存放在qx1中)
void Multiply(Polynominal* px, Polynominal* qx) {
    Polynominal qx1, qx2;
    PNode* q1, * q2, * q3, * q4, * pre = (PNode*)malloc(sizeof(PNode)), * q;
    qx1.head = (PNode*)malloc(sizeof(PNode));       //生成新多項(xiàng)式qx1
    qx1.head->exp = -1;
    qx1.head->link = qx1.head;                      //qx1改造成循環(huán)鏈表
    q1 = px->head;                            //q1指向px的第一項(xiàng)
    q2 = qx->head;                            //q2指向qx的第一項(xiàng)
    while (q2->exp != -1) {                           //當(dāng)q2的指數(shù)不為-1時(shí),px先和qx的每一項(xiàng)相乘
        q3 = (PNode*)malloc(sizeof(PNode));         //q3存放相乘的結(jié)果
        // 系數(shù)相乘，階數(shù)相加
        q3->coef = q1->coef * q2->coef;
        q3->exp = q1->exp + q2->exp;

        if (qx1.head->link->exp == -1) {              //q3插入到qx1多項(xiàng)式第一項(xiàng)中
            q3->link = qx1.head->link;
            qx1.head->link = q3;
            pre = qx1.head->link;
        }

        else {                                       //q3插入到qx1多項(xiàng)式最后一項(xiàng)中
            q3->link = qx1.head;
            pre->link = q3;
            pre = pre->link;
        }

        q2 = q2->link;
    }
    // q1 指向 q1表達(dá)式的下一項(xiàng)
    q1 = q1->link;                                 //q1后移一位
    while (q1->exp != -1) {                          //px剩下來每一項(xiàng)都和qx每一項(xiàng)相乘
        q2 = q2->link;
        qx2.head = (PNode*)malloc(sizeof(PNode));  //生成新多項(xiàng)式qx2
        qx2.head->exp = -1;
        qx2.head->link = qx2.head;                // 指向自己

        // 遍歷 q2 的每一項(xiàng)
        while (q2->exp != -1) {
            q4 = (PNode*)malloc(sizeof(PNode));
            q4->coef = q1->coef * q2->coef;
            q4->exp = q1->exp + q2->exp;
            if (qx2.head->link->exp == -1) {
                q4->link = qx2.head->link;
                qx2.head->link = q4;
                pre = qx2.head->link;
            }
            else {
                q4->link = qx2.head;
                pre->link = q4;
                pre = pre->link;
            }
            q2 = q2->link;
        }
        Add(&qx2, &qx1);                            //合并同類項(xiàng)
        q1 = q1->link;
    }
    Output(qx1);
}


int main() {
    Polynominal p, q;
    int x;
    printf("請(qǐng)輸入第一個(gè)表達(dá)式:\n");
    Create(&p);
    Output(p);
    printf("\n\n請(qǐng)輸入第二個(gè)表達(dá)式\n");
    Create(&q);
    Output(q);
    printf("請(qǐng)輸入選項(xiàng)\n 1: 加法   2:乘法\n");
    scanf_s("%d", &x);
    switch (x) {       
    case 0: break;
        //選擇加法還是乘法功能
    case 1:printf("加法結(jié)果:\n");
        Add(&p, &q);
        Output(q);
        break;
    case 2:printf("乘法結(jié)果:\n");
        Multiply(&p, &q);
        break;
    default: break;
    }
    return 0;
}

/*
* typedef struct PNode {
    int coef;             //系數(shù)
    int exp;              //指數(shù)
    struct PNode* link;
}PNode;

typedef struct {
    struct PNode* head;
}Polynominal;
* 
先創(chuàng)建結(jié)構(gòu)體PNode 表示多項(xiàng)式的某一項(xiàng)，內(nèi)含三個(gè)成員變量，分別是coef(項(xiàng)的系數(shù))，exp(項(xiàng)的階數(shù))，link(下一項(xiàng)的地址)

再創(chuàng)建多項(xiàng)式結(jié)構(gòu)體Polynominal，內(nèi)含一個(gè)成員變量head（多項(xiàng)式首項(xiàng)的地址）

算法：
1、先創(chuàng)建兩個(gè)表達(dá)式結(jié)構(gòu)體指針變量Polynominal* p q;
2、p q 分別調(diào)用 Creat(Polynominal*) 函數(shù)對(duì)多形式進(jìn)行初始化 
初始化算法如下：
為多項(xiàng)式的頭指針即多項(xiàng)式結(jié)構(gòu)體的成員變量進(jìn)行動(dòng)態(tài)空間申請(qǐng)。將頭指針即多項(xiàng)式的第一項(xiàng)的階數(shù)初始化為-1
從控制臺(tái)獲取用戶要輸入的多項(xiàng)式的項(xiàng)數(shù)，記為nn
循環(huán) nn 次，用戶依次輸入系數(shù)，階數(shù)，系數(shù)，階數(shù)······ 直至輸入完畢
算法對(duì)輸入的多項(xiàng)式實(shí)行按該項(xiàng)階數(shù)降序的順序進(jìn)行順序存儲(chǔ)。
算法實(shí)現(xiàn)過程是：

1、多項(xiàng)式的創(chuàng)建
*/

到了這里，關(guān)于南京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一（線性表的基本運(yùn)算及多項(xiàng)式的算術(shù)運(yùn)算）（代碼篇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！