【C语言】数据结构实验报告--单链表_数据结构单链表实验

#include<stdio.h>
#include"linklist.cpp"

void Split(LinkNode *&L)
{
	LinkNode *pre,*p;
	if(L->next == NULL || L->next->next == NULL)
		return;
	int x = L->next->data; // 将首节点赋给x
	pre = L->next;
	p = pre->next;
	while(p!=NULL)
	{
		if(p->data < x)
		{
			pre->next = p->next;
			p->next = L->next; // 将节点p插到表头 
			L->next = p;
			p = pre->next;
		}
		else
		{
			pre = p; // p,pre同步后移 
			p= pre->next;
		}
	 } 
}
int main()
{
	LinkNode *L;
	ElemType a[] = {23,41,2,15,12,90,66,9};
	int n = sizeof(a)/sizeof(int); // 求整型数组的长度 
	CreateListR(L,a,n); // 创建链表 
	printf("L: "); DispList(L);
	printf("以首节点进行划分\n");
	Split(L);
	printf("L: "); DispList(L);
	DestroyList(L); // 销毁链表 
	return 0; 
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

这里的linklist.cpp是一个单独保存单链表所有基本操作的C文件

运行结果：

二.：将两个单链表合并成一个单链表

#include<stdio.h>
#include "linklist.cpp"
void Union(LinkNode *L1,LinkNode *L2,LinkNode *&L3)
{
	LinkNode *p1 = L1->next,*p2 = L2->next,*r,*s;
	L3 = (LinkNode *)malloc(sizeof(LinkNode));
	r = L3;
	while(p1!=NULL && p2!=NULL)
	{
		s = (LinkNode *)malloc(sizeof(LinkNode));
		s->data = p1->data;
		r->next = s;
		r = s;
		p1= p1->next;
		s = (LinkNode *)malloc(sizeof(LinkNode));
		s->data = p2->data;
		r->next = s;
		r = s;
		p2= p2->next; 
	}
	while(p1!=NULL)
	{
		s = (LinkNode *)malloc(sizeof(LinkNode));
		s->data = p1->data;
		r->next = s;
		r = s;
		p1= p1->next;
	}
	while(p2!=NULL)
	{
		s = (LinkNode *)malloc(sizeof(LinkNode));
		s->data = p2->data;
		r->next = s;
		r = s;
		p2= p2->next;
	}
	r->next = NULL;
 } 
 int main()
 {
 	LinkNode *L1,*L2,*L3;
	ElemType a[] = {1,2,3,4,5,6,7};
	ElemType b[] = {8,9,10,11,12,13,14,15};
	int n = sizeof(a)/sizeof(int); // 求整型数组的长度 
	CreateListR(L1,a,n); // 创建链表 
	int m = sizeof(b)/sizeof(int); // 求整型数组的长度 
	CreateListR(L2,b,m); 	
	printf("L1: "); DispList(L1);
	printf("\nL2: "); DispList(L2);
	printf("将L1和L2合并：\n");
	Union(L1,L2,L3);
	printf("L3: "); DispList(L3);
	DestroyList(L3); // 销毁链表 
	return 0;
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

三.实现两个多项式相乘，用单链表存储一元单项式，并实现两个多项式相乘的运算

#include<stdio.h>
#include<stdlib.h>
#include<math.h> 
 
#define LEN sizeof(Poly)
 
typedef struct term{
    float coef;        //系数 
    int expn;        //指数 
    struct term *next;
}Poly,*Link;

int LocateElem(Link p, Link s, Link &q); 
void CreatePolyn(Link &p,int m);    //创建多项式 
void PrintPolyn(Link p);            //打印多项式（表示）            
Link Reverse(Link p);                //逆置多项式 
Link MultiplyPolyn(Link A,Link B);    //多项式相乘 

int main()
{
    Link P1,P2,P3;    //多项式 
    int L1,L2;        //多项式长度 
    printf("请输入第一个多项式的项数：");
    scanf("%d",&L1);
    CreatePolyn(P1,L1);
    printf("第一个多项式为：");
    printf("P1(X)=");
    PrintPolyn(P1);
    printf("请输入第二个多项式的项数：");
    scanf("%d",&L2);
    CreatePolyn(P2,L2);
    printf("第二个多项式为：");
    printf("P2(X)=");
    PrintPolyn(P2); 
    printf("\n");

             printf("两个一元多项式相乘：   ");
             printf("P1(X)*P2(X)=");
             P3=MultiplyPolyn(P1, P2);
            PrintPolyn(P3);
    return 0;
}
int LocateElem(Link p, Link s, Link &q){ 
    Link p1 = p->next;
    Link p2 = p;
    while(p1){
        if(s->expn > p1->expn){
            p1 = p1->next;
            p2 = p2->next;
        }else if(s->expn == p1->expn){
            q = p1; 
            return 1;
        }else{
            q = p2;
            return 0;
        }
    }
    if(!p1){
        q = p2;
        return 0;
    }
}
 
void CreatePolyn(Link &p,int m) 
{
    Link s,q;
    int i;
    p=(Link)malloc(LEN);
    p->next=NULL;
    for(i=0;i<m;i++)
    {
        s=(Link)malloc(LEN);
        printf("输入系数和指数（以空格隔开）:");
        scanf("%f %d", &s->coef, &s->expn);
        if(!LocateElem(p, s, q)){    //若没有相同指数项，则链入 
            s->next = q->next;
            q->next = s;
        }else{                        //若有相同指数项，则系数相加                        
            q->coef+=s->coef;
        }
    }
}
void PrintPolyn(Link p)
//打印显示多项式 
{
    Link s;
    s = p->next;
    while(s)
    {
            printf(" %.2f X^%d", s->coef, s->expn);
            s = s->next;
            if(s!=NULL)  
                if(s->coef>=0) printf(" +");
                //若下一项系数为正，则打印'+',否则不打印 
    }
    printf("\n");
}
Link Reverse(Link p) 
{
    Link head=p; 
    Link q1,q2;
    q2=head->next;
    head->next=NULL;//断开头结点与第一个结点 
    while(q2)
    {
        q1=q2;      
        q2=q2->next; 
        q1->next=head->next; //头插 
        head->next=q1;  
    }      
    return head;//返回链表逆置后的头结点 
}
Link MultiplyPolyn(Link A,Link B)
{
  Link pa,pb,pc,s,head;
  int k,maxExpn,minExpn;
  float coef;
  
  head=(Link)malloc(LEN);//头结点 
  head->next=NULL;
  
  if(A->next!=NULL&&B->next!=NULL){
      minExpn=A->next->expn+B->next->expn; //minExpn为两个多项式中指数和的最小值 
     A=Reverse(A);//将A降幂排列 
    B=Reverse(B);//将B降幂排列 
      maxExpn=A->next->expn+B->next->expn; //maxExpn为两个多项式中指数和的最大值
  }
  else{
          return head;
  }       
   pc=head;
   B=Reverse(B);//将B升幂排列 
   for(k = maxExpn;k>=minExpn;k--){ //多项式的乘积指数范围为：minExpn~maxExpn
           //根据两项的指数和使每一次循环都得到新多项式中一项  
           pa = A->next;
           while(pa !=NULL&&pa->expn>k){  //找到pa的位置 
               pa = pa->next;
           }
           pb = B->next;
           while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k){//如果指数和和小于k，pb后移结点 
               pb = pb->next;
           }
        coef=0.0;
        while(pa!=NULL&&pb!=NULL){
            if(pa->expn+pb->expn==k){ //如果指数和等于k,系数和累加，且pa，pb均后移结点 
                coef+=pa->coef*pb->coef;
                pa=pa->next;
                pb=pb->next;
            }
            else if(pa->expn+pb->expn>k){//如果指数和大于k，pb后移结点
                pa = pa->next;
            }
            else{//如果指数和和小于k，pb后移结点
                    pb = pb->next;
            }    
        }
        if(coef!=0.0){
        //如果系数和不为0，则生成新结点，将系数和指数赋给新结点后插入到新多项式中 
            s=(Link)malloc(LEN);
            s->coef=coef;
            s->expn=k;
            s->next=pc->next;
            pc->next=s;
            pc=s;
        }
   }
   B = Reverse(B);
   head=Reverse(head);
   return head;    //返回新多项式的头结点 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

运行结果：