Question

数据结构的问题，如何用c语言实现

学了线性表那一章，树上都讲的是伪代码，那么用c语言实现的时候，是如何实现呢？用数组和结构体的形式吗？比如编写一元多项式算法？

Answer 1

#include <stdio.h>
#include <stdlib.h>
struct node
{
int coef,exp;
struct node *next;
} *La,*Lb,*Lc;
void add()
{
node *p,*q;
int i;
p=Lc=(node *)malloc(sizeof(node));
La=La->next;Lb=Lb->next;
while(La&&Lb)
{
if(La->exp==Lb->exp)
{
if(La->coef+Lb->coef!=0)
{
q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=La->coef+Lb->coef;
p->exp=La->exp;
}
La=La->next;Lb=Lb->next;
}
else if(La->exp<Lb->exp)
{
q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=La->coef;
p->exp=La->exp;
La=La->next;
}
else
{
q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=Lb->coef;
p->exp=Lb->exp;
Lb=Lb->next;
}
}
while(La)
{
q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=La->coef;
p->exp=La->exp;
La=La->next;
}
while(Lb)
{
q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=Lb->coef;
p->exp=Lb->exp;
Lb=Lb->next;
}
p->next=NULL;
}
int main ()
{
node *p,*q,*pa;
int i,j,n,m,e,c;
scanf("%d",&n);
p=La=(node *)malloc(sizeof(node));
for(i=1;i<=n;i++)
{
q=(node *)malloc(sizeof(node));
scanf("%d%d",&c,&e);
q->coef=c;
q->exp=e;
p->next=q;
p=q;
}
p->next=NULL;
scanf("%d",&m);
p=Lb=(node *)malloc(sizeof(node));
for(i=1;i<=m;i++)
{
q=(node *)malloc(sizeof(node));
scanf("%d%d",&c,&e);
q->coef=c;
q->exp=e;
p->next=q;
p=q;
}
p->next=NULL;
add();
pa=Lc->next;
while(pa)
{
printf("%d %d\n",pa->coef,pa->exp);
pa=pa->next;
}
}

/*
以前自己实现的代码，功能是两个一元多项式相加。
输入格式：
输入数据有多组，对于每组测试数据，第一行一个整数n，表示第一个多项式La的项数；接下来n行，每行表示多项式的一项，包含两个元素，表示系数和指数；接下来一个整数m，表示第二个多项式Lb的项数；接下来m行，每行表示多项式的一项，包含两个元素，表示系数和指数；

输出格式：
La与Lb相加之后的多项式。
按指数从小到大输出，每行一项，用空格把系数和指数分开。
*/

追问

q=(node *)malloc(sizeof(node));
p->next=q;p=q;
p->coef=La->coef;
p->exp=La->exp;
La=La->next;
这里p->next=q;p=q;是不是应该改成q=p呀？

Answer 2

以前写的多项式运算

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

typedef struct _PolyNode {
	int index;
	int cofficient;
} NodeType;

typedef struct _polynomial {
	NodeType data;
    struct _polynomial *next;
} Polynomial;

void append(Polynomial* head, NodeType data) {
	Polynomial *p = (Polynomial*)malloc(sizeof(Polynomial));
	p->data = data;
	p->next = head->next;
	head->next = p;
}

void input(Polynomial* head) {
	NodeType data;
	do {
		scanf("%d%d", &data.cofficient, &data.index);
		append(head, data);
	} while(data.cofficient != 0 && data.index != -1);
}

/**
 * 合并同类项并去除系数为0的项
 */
void merge(Polynomial *head) {
	Polynomial *p;
	for(p = head->next; p->next; p = p->next)
		if(p->data.index == p->next->data.index) {
			p->data.cofficient += p->next->data.cofficient;
			p->next->data.cofficient = 0;
		}
	for(p = head; p->next;)
		if(p->next->data.cofficient == 0) {
			Polynomial *q;
			q = p->next;
			p->next = q->next;
			free(q);
		}
		else
			p = p->next;
}

/**
 * 按指数从高到低排序
 */
void sort(Polynomial *head) {
	Polynomial *p, *q;
	for(p = head->next; p->next; p = p->next) {
		NodeType t = p->data;
		for(q = p->next; q; q = q->next) {
			if(t.index < q->data.index) {
				p->data = q->data;
				q->data = t;
				t = p->data;
			}
		}
	}
}

Polynomial* add(Polynomial *a, Polynomial *b) {
	Polynomial *p, *ret = (Polynomial*)malloc(sizeof(Polynomial));
	ret->next = NULL;
	for(p = a->next; p; p = p->next)
		append(ret, p->data);
	for(p = b->next; p; p = p->next)
		append(ret, p->data);
	sort(ret);
	merge(ret);
	return ret;
}

Polynomial* multiply(Polynomial *a, Polynomial *b) {
	Polynomial *p, *q, *ret = (Polynomial*)malloc(sizeof(Polynomial));
	ret->next = NULL;
	for(p = a->next; p; p = p->next)
		for(q = b->next; q; q = q->next) {
			NodeType data = {p->data.index + q->data.index, p->data.cofficient * q->data.cofficient};
			append(ret, data);
		}
	sort(ret);
	merge(ret);
	return ret;
}

void display(Polynomial *head) {
	Polynomial *p;
	for(p = head->next; p; p = p->next) {
		if(p->data.cofficient < 0)
			printf("-");
		else if(p != head->next)
			printf("+");
		if(!(abs(p->data.cofficient) == 1 && p->data.index > 0))
			printf("%d", abs(p->data.cofficient));
		if(p->data.index > 0) {
			printf("X");
			if(p->data.index > 1)
				printf("^%d", p->data.index);
		}
	}
	printf("\n");
}

int main() {
	Polynomial *a = (Polynomial*)malloc(sizeof(Polynomial)),
			   *b = (Polynomial*)malloc(sizeof(Polynomial));
	input(a);
	input(b);
	display(a);
	display(b);
	display(add(a, b));
	display(multiply(a, b));
	return 0;
}

Answer 3

具体可以参考下面的书籍 里面有详细内容，网上可以查到该书籍：
《数据结构(c语言版)：1000个问题与解答》

Answer 4

线性表就是数组链表之类的吧。学了太久了，我也记不清了