数据结构第二次实验

1、顺序表逆置

设有一个线性表 (e0,e1, …, en-2, en-1) 存放在线性顺序表L中。请编写函数将这个线性表原地逆置，即将n个元素内容置换为 (en-1, en-2, …, e1, e0)。

函数原型为：void ReverseSqList(SqList &L ){…}

首先构建顺序表：

在创建时获得顺序表长度为n，顺序表为arr[100];

将n和arr[100]的首地址，即arr传入倒置函数ReverArr( n , arr );

倒置函数获得顺序表长度n后，计算得交换次数为j=n/2;

接下来用for(int i=0;i<j;i++)遍历顺序表，并每一次遍历时，将顺序表前部分数据和后部分数据调换，即

{

temp = arr[i];

  arr[i] = arr[n - 1 - i];

  arr[n - 1 - i] = temp;

}

最后遍历顺序表并输出即完成倒置；

代码：

#include <iostream>
#include <cstring>
using namespace std;

void ReverArr(int n, int arr[]);

int main() {
	int n;
	int arr[100];
	memset(arr, '0', sizeof(arr));
	cout << "请输入线性表长度:";
	cin >> n;
	cout << "***********" << endl;
	for (int i = 0; i < n; i++)
	{

		//cout << "***********" << endl;
		arr[i] =i+1;
		cout << arr[i]<<" ";
	}
	ReverArr(n, arr);
	return 0;
}

void ReverArr(int n, int arr[]) {
	int j = n / 2;
	int temp;
	for (int i = 0; i <= j; i++)
	{
		temp = arr[i];
		arr[i] = arr[n - 1 - i];
		arr[n - 1 - i] = temp;
	}
	for (int i = 0; i < n; i++)
	{
		cout << arr[i]<<" ";
	}
}

2、链表逆置

将一个链表逆置，函数原型为：void ReverseLinkList(LinkList &L)。

最后直到最后一个逆置结束就完成了整个链表的逆置。

全部代码：

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

typedef struct ReverseLinkList
{
    int data;
    struct ReverseLinkList *next;
}*ReverseLinkList;

void nizhi(ReverseLinkList L);

int main( ){
    struct ReverseLinkList* head = (struct ReverseLinkList*)malloc(
        sizeof(struct ReverseLinkList));
    head->next = NULL;
    struct ReverseLinkList* p;
    int n;
    printf("请输入链表长度：\n");
    scanf("%d", &n);
    printf("输入数据：\n");
    for (int i = 0; i < n; i++)
    {
        struct ReverseLinkList* s = (struct ReverseLinkList*)malloc(sizeof(struct ReverseLinkList));
        scanf("%d", &s->data);
        s->next = head->next; 
        head->next = s;
    }

    p = head;
    ReverseLinkList s = p;
    printf("原链表为:");
    while (p->next != NULL)
    {
        printf("%d", p->next->data);
        p = p->next;
        if (p->next != NULL)printf(" -> ");
    }
    printf("\n");

    nizhi(s);

    printf("逆置后的链表为：");
    while (s->next != NULL)
    {
        printf("%d", s->next->data);
        s = s->next;
        if (s->next != NULL)printf(" -> ");
    }
    printf("\n");
    return 0;
}

void nizhi(ReverseLinkList L) {
    ReverseLinkList s, p;
    p = L->next;
    L->next = NULL;

    while (p)
    {
        s = p;
        p = p->next;
        s->next = L->next;
        L->next = s;
    }
}

1、创建结构体：

typedef struct ReverseLinkList
{
    int data;
    struct ReverseLinkList *next;
}*ReverseLinkList;

2、创建逆置函数：

void nizhi(ReverseLinkList L) {
    ReverseLinkList s, p;
    p = L->next;
    L->next = NULL;
//建议结合上图一起看
    while (p)
    {
        s = p;
        p = p->next;
        s->next = L->next;
        L->next = s;
    }
}

3、main函数：

int main( ){
    struct ReverseLinkList* head = (struct ReverseLinkList*)malloc(sizeof(struct ReverseLinkList));
    head->next = NULL;
    struct ReverseLinkList* p;
    int n;
    printf("请输入链表长度：\n");
    scanf("%d", &n);
    printf("输入数据：\n");
    for (int i = 0; i < n; i++)
    {
        struct ReverseLinkList* s = (struct ReverseLinkList*)malloc(sizeof(struct ReverseLinkList));
        scanf("%d", &s->data);
        s->next = head->next; 
        head->next = s;
    }

    p = head;
    ReverseLinkList s = p;
    printf("原链表为:");
    while (p->next != NULL)
    {
        printf("%d", p->next->data);
        p = p->next;
        if (p->next != NULL)printf(" -> ");
    }
    printf("\n");

    nizhi(s);

    printf("逆置后的链表为：");
    while (s->next != NULL)
    {
        printf("%d", s->next->data);
        s = s->next;
        if (s->next != NULL)printf(" -> ");
    }
    printf("\n");
    return 0;
}

3、编程实现求两多项式的和多项式

A (x) = 7 + 3x + 9x8 + 5x17

B (x) = 8x + 22x7 – 9x8

全部代码：

//今天就写到这里了，累了，睡觉。
#include <stdio.h>
#include <stdlib.h>
typedef struct PPP{
    float XiShu;
    int ZhiShu;
    struct PPP *next;
}PPP,*PList;

void CreatePPP(PList L, int m); 

PList HeBingPPP(PList head_1 , PList head_2);

void PrintPPP_2(PList q);

void PrintPPP_1(PList L);


int main(){
    PList head_1,head_2,head_3;
    int m,n;
  
    printf("请输入多项式A的项数:");
    scanf("%d",&n);
    head_1 = (PList)malloc(sizeof(PPP));
    CreatePPP(head_1,n);
  
    printf("请输入多项式B的项数:");
    scanf("%d",&m);
    head_2 = (PList)malloc(sizeof(PPP));
    CreatePPP(head_2,m);
  
    head_3 = HeBingPPP(head_1,head_2);
    printf("\n两个多项式合并后为：");
    PrintPPP_1(head_3);
    return 0;
}

void CreatePPP(PList L, int m){
    int i;
    float XiShu;
    int ZhiShu;
    PList tail,NewNext;
    L->XiShu = m;
    L->ZhiShu = -1;
    tail = L;
    for(i=1 ; i<=m ; i++){
         NewNext = (PList)malloc(sizeof(PPP));
         printf("请分别输入系数和指数:");
         scanf("%f",&XiShu);
         scanf("%d",&ZhiShu);
         NewNext->XiShu = XiShu;
         NewNext->ZhiShu = ZhiShu;
         NewNext->next = NULL;
         tail->next = NewNext;
         tail = NewNext;
    }
}

PList HeBingPPP(PList head_1 , PList head_2){
    int x,len;
    float y;
    PList head_3,pa,pb,pc,u;
    head_3 = head_1;
    len = 0;
    pc = head_3;
   
    pa = head_1->next;
    pb = head_2->next;
  
    while(pa && pb){
        x = pa->ZhiShu-pb->ZhiShu;
    
        if(x<0){
        
            pc = pa;
            len++;
            pa = pa->next;
        }
    
        else if(x == 0){
            y = pa->XiShu + pb->XiShu;
            if(y!=0.0){
            
                pa->XiShu = y;
                pc = pa;
                len++;
            }
        
            else{
                pc->next=pa->next;
                free(pa);
            }
       
            pa = pc->next;
            u = pb;
            pb = pb ->next;
            free(u);
        }
   
        else{
            u = pb->next;
            pb->next= pa;
            pc->next=pb;
            pc = pb;
            len++;
            pb = u;
        }
    }
  
    if(pb){
        pc->next = pb;
    }
  
    while(pc){
        pc = pc->next;
        if(pc){
            len++;
        }
    }
  
    head_3->XiShu = len;
  
    free(head_2);
    return head_3;
}


void PrintPPP_2(PList q){
    if(q->ZhiShu == 0){
        printf("%.0f",q->XiShu);
    }
    else if(q->ZhiShu == 1){
        if(q->XiShu == 1){
            printf("x");
        }
        else if (q->XiShu == -1){
            printf("-X");
        }
        else{
            printf("%.0f",q->XiShu);
            printf("X");
        }
    }
    else if (q->XiShu == 1){
        printf("X^%d",q->ZhiShu);
    }
    else if(q->XiShu == -1){
        printf("-X^%d",q->ZhiShu);
    }
    else{
        printf("%.0fX^%d",q->XiShu,q->ZhiShu);
    }
}

void PrintPPP_1(PList L){
    int n;
    PList p;
    p = L->next;
    n = 0;
    while(p){
        n++;
        if(n == 1){
            PrintPPP_2(p);
        }else if(p->XiShu>0){
            printf("+");
            PrintPPP_2(p);
        }else{
            PrintPPP_2(p);
        }
        p = p->next;
    }
}