- 浏览: 269808 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (111)
- Ajax (3)
- Oracle (10)
- 云计算 (0)
- Java (10)
- jquery (3)
- 杂 (8)
- 算法导论 (1)
- Flex (3)
- JDBC (1)
- GIS概念 (0)
- CSS (1)
- CVS Eclipse (1)
- Hibernate (1)
- Struts2 (5)
- Servlet JSP (2)
- 数据结构与问题求解 (1)
- CentOS (3)
- C语言名题百则 (4)
- 设计模式 (1)
- Ubuntu (3)
- JavaScript (15)
- C语言 (12)
- 数据结构 (8)
- DOM (4)
- UML (2)
- C语言,C++ (3)
- MongoDB (6)
- 操作系统原理 (6)
- 计算机网络 (0)
- node.js (1)
- FreeBSD (1)
- MySQL (1)
- 通知帖 (0)
- 版本控制 (2)
- Linux (1)
- Vim (1)
- 形式语言与自动机 (0)
- 搜索引擎 (2)
- Haskell (4)
最新评论
-
arther8888:
niedj 写道请问,关于CachedThreadPool的方 ...
Java并发包中的几种ExecutorService -
Lyleluo:
深圳java群 397083120 求职,学习全包,外加小美女 ...
Java数组初始化 -
happyzjj:
楼主讲的很详细,不过关于CachedThreadPool我试的 ...
Java并发包中的几种ExecutorService -
niedj:
请问,关于CachedThreadPool的方式,楼主是否自己 ...
Java并发包中的几种ExecutorService -
garyzhang2681:
2.实现Runnable接口有试过t1.start(); t1 ...
Java多线程笔记1——多线程两种实现方式
大一的时候我们专业开了一门C语言限选课,老师觉得指针太难,所以不讲指针。大三的时候学数据结构,考虑到数据结构比较难,老师不要求代码实现。就这样,两门比较重要的课就这样浑浑噩噩的过去了。后来学Java,算是学的还行,也独立的做过一些导师的项目。只是在找工作的时候,才发现笔试题、面试题到处都是C、C++和数据结构的题。多多少少也因此碰了不少壁。不管怎么样,自己还年轻,以前没学好,现在学也不晚。
这一系列博客,我会分别用Java和C实现一些数据结构基本操作以及书中提到的问题。一方面算是巩固Java,另一方面算是重新学习数据结构和C语言吧。
教材:《数据结构与算法分析——C语言描述》(第二版)(Mark Allen Weiss著,冯舜玺译)(机械工业出版社)。
1.链表的基本操作
链表数据结构的定义:由于链表一方面需要在节点中存储数据,另一方面还需要存储"线索",因此,通常采用结构体定义链表节点数据类型。
struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; struct Node { ElementType Element; Position Next; };
链表的操作不算太多,下面是一些常用的操作:
//创建链表 List CreateList(); //遍历链表 void TraverseList(List L); //清空链表 List MakeEmpty(List L); //判断给定列表是否为空 int IsEmpty(List L); //判断节点在给定链表中是否为空 int IsLast(Position P, List L); //在指定的链表中查找给定元素。 //存在则返回其第一次出现的位置,不存在则返回NULL Position Find(ElementType X, List L); //删除链表中的某个元素 void Delete(ElementType X, List L); //在指定链表中查找给定元素的前驱节点 Position FindPrevious(ElementType X, List L); //在链表给定位置的后面插入元素 void Insert(ElementType X, List L, Position P); //删除链表 void DeleteList(List L); //返回链表的头结点 Position Header(List L); //返回链表第一个数据元素节点 Position First(List L); //返回当前位置的下一个位置 Position Advance(Position P); //获取当前位置元素的值 ElementType Retrive(Position P);
下面是实现基本操作以及简单使用的一个完整的例子。
#include <stdio.h> #include <stdlib.h> struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; struct Node { ElementType Element; Position Next; }; //创建链表 List CreateList(); //遍历链表 void TraverseList(List L); //清空链表 List MakeEmpty(List L); //判断给定列表是否为空 int IsEmpty(List L); //判断节点在给定链表中是否为空 int IsLast(Position P, List L); //在指定的链表中查找给定元素。 //存在则返回其第一次出现的位置,不存在则返回NULL Position Find(ElementType X, List L); //删除链表中的某个元素 void Delete(ElementType X, List L); //在指定链表中查找给定元素的前驱节点 Position FindPrevious(ElementType X, List L); //在链表给定位置的后面插入元素 void Insert(ElementType X, List L, Position P); //删除链表 void DeleteList(List L); //返回链表的头结点 Position Header(List L); //返回链表第一个数据元素节点 Position First(List L); //返回当前位置的下一个位置 Position Advance(Position P); //获取当前位置元素的值 ElementType Retrive(Position P); int IsEmpty(List L) { return L->Next == NULL; } int IsLast(Position P, List L) { return P->Next == NULL; } Position Find(ElementType X, List L) { Position P = L->Next; while(P != NULL && P->Element != X) { P = P->Next; } return P; } void Delete(ElementType X, List L) { Position P,TmpCell; P = FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell = P->Next; P->Next = TmpCell->Next; free(TmpCell); } } Position FindPrevious(ElementType X, List L) { Position P = L; while(P->Next != NULL && P->Next->Element != X) { P = P->Next; } return P; } void Insert(ElementType X, List L, Position P) { Position TmpCell; TmpCell = malloc(sizeof(struct Node)); if(TmpCell == NULL) { printf("Out of space!\n"); return; } TmpCell->Element = X; TmpCell->Next = P->Next; P->Next = TmpCell; } void DeleteList(List L) { Position P,Tmp; P = L->Next; L->Next = NULL; while(P != NULL) { Tmp = P->Next; free(P); P = Tmp; } } Position Header(List L) { return L; } Position First(List L) { return L->Next; } Position Advance(Position P) { return P->Next; } ElementType Retrive(Position P) { return P->Element; } List CreateList() { int i; Position P,Tmp; List L = malloc(sizeof(struct Node)); P = L; for(i = 0; i < 5; i++) { Tmp = malloc(sizeof(struct Node)); Tmp->Element = i; P->Next = Tmp; P = Tmp; } P->Next = NULL; return L; } void TraverseList(List L) { Position P; P = L->Next; while(P != NULL) { printf("%d\n",P->Element); P = P->Next; } } int main(void) { //创建链表 List L = CreateList(); //查找元素1在链表中的位置 Position P = Find(1,L); //在元素1后面插入元素8 Insert(8,L,P); //查找元素8前驱结点 P = FindPrevious(8,L); //遍历链表 TraverseList(L); return 0; }
2.一元N次多项式相加
对于两个一元多项式,如果需要对他们进行多项式相加操作,常见的两种思路如下:(1)对于一个多项式,保存其最高项次数HighPowder,以及一个该多项式对应次数分别为0-HighPowder的各项的系数的数组()。(2)多项式中系数不为零的每一项,保存其系数与该项的次数。下面分别用这两种思路实现一元多项式加法操作。
思路一:
数据结构定义:
typedef struct Poly { int CoeffArray[11]; int HighPower; } *Polynomial;
实现代码:
#include <stdio.h> #include <stdlib.h> typedef struct Poly { int CoeffArray[11]; int HighPower; } *Polynomial; void ZeroPolynomial(Polynomial Poly) { int i; for(i = 0; i < 11; i++) { Poly->CoeffArray[i] = 0; } Poly->HighPower = 0; } void AddPolynomial(Polynomial Poly1,Polynomial Poly2, Polynomial PolySum) { int i; ZeroPolynomial(PolySum); PolySum->HighPower = Poly1->HighPower > Poly2->HighPower? Poly1->HighPower:Poly2->HighPower; for(i = PolySum->HighPower; i >= 0 ; i--) { PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i]; } } int main(void) { int i,j,k; Polynomial P1,P2,Sum; P1 = malloc(sizeof(struct Poly)); P2 = malloc(sizeof(struct Poly)); Sum = malloc(sizeof(struct Poly)); //初始化 ZeroPolynomial(P1); ZeroPolynomial(P2); P1->HighPower = 10; for(i = 10; i >= 0; i--) { P1->CoeffArray[i] = i; } P2->HighPower = 8; for(j = 8; j >=0; j--) { P2->CoeffArray[j] = j; } P2->CoeffArray[8] = 8; AddPolynomial(P1,P2,Sum); printf("The high power of the Polynomial is %d\n",Sum->HighPower); for(k = 0; k <= 10; k++) { printf("The Coeff of power %d is %d\n",k,Sum->CoeffArray[k]); } return 0; }
思路二:
数据结构:
typedef struct PolyNode *PtrToNode; //定义链表节点,也就是多项式中的某一项; typedef struct PolyNode { int Coeff; int Exponent; PtrToNode Next; } PolyNode;
实现代码:
#include <stdio.h> #include <stdlib.h> typedef struct PolyNode *PtrToNode; //定义链表节点,也就是多项式中的某一项; typedef struct PolyNode { int Coeff; int Exponent; PtrToNode Next; } PolyNode; typedef PtrToNode Polynomial; /************************************************************ *多项式相加的函数: *P、Q为存储两个多项式各项的单链表(含头结点) *Sum为多项式相加结果存放的单链表 * ************************************************************/ void AddPolynomial(Polynomial P,Polynomial Q,Polynomial Sum) { Polynomial PIndex,QIndex,SumIndex; PIndex = P->Next; QIndex = Q->Next; SumIndex = Sum; while(!(PIndex == NULL && QIndex == NULL)) { if(PIndex==NULL) { SumIndex->Next = QIndex; QIndex = QIndex->Next; SumIndex = SumIndex->Next; } else if(QIndex == NULL) { SumIndex->Next = PIndex; PIndex = PIndex->Next; SumIndex = SumIndex->Next; } else { if(PIndex->Exponent > QIndex->Exponent) { SumIndex->Next = PIndex; PIndex = PIndex->Next; SumIndex = SumIndex->Next; //continue在判断下面if条件时会有异常,类似Java //的空引用异常 continue; } if(PIndex->Exponent == QIndex->Exponent) { Polynomial PP = malloc(sizeof(struct PolyNode)); PP->Exponent = PIndex->Exponent; PP->Coeff = PIndex->Coeff + QIndex->Coeff; SumIndex->Next = PP; PIndex = PIndex->Next; QIndex = QIndex->Next; SumIndex = SumIndex->Next; continue; } if(PIndex->Exponent < QIndex->Exponent) { SumIndex->Next = QIndex; QIndex = QIndex->Next; SumIndex = SumIndex->Next; continue; } } } SumIndex->Next = NULL; } /************************************************************ *遍历单链表(含头结点)函数: *P:待遍历的链表 *************************************************************/ void TraversePolynomial(Polynomial P) { Polynomial Tmp = P->Next; while(Tmp != NULL) { printf("Coeff is %d and Exponent is %d\n",Tmp->Coeff,Tmp->Exponent); Tmp = Tmp->Next; } } int main(void) { Polynomial Poly1,Poly2,Poly3,Poly11,Poly22; int i,j; Poly1 = malloc(sizeof(struct PolyNode)); Poly2 = malloc(sizeof(struct PolyNode)); Poly3 = malloc(sizeof(struct PolyNode)); Poly11 = Poly1; Poly22 = Poly2; //创建两个链表时,需要保证是按照指数递减的方式构造的 for(i = 5;i >= 1;i--) { Polynomial Tmp = malloc(sizeof(struct PolyNode)); Tmp->Coeff = i; Tmp->Exponent = i; Poly11->Next = Tmp; Poly11 = Poly11->Next; } Poly11->Next = NULL; for(j = 11;j >= 3;j--) { Polynomial Tmp = malloc(sizeof(struct PolyNode)); Tmp->Coeff = j; Tmp->Exponent = j; Poly22->Next = Tmp; Poly22 = Poly22->Next; } Poly22->Next = NULL; TraversePolynomial(Poly1); printf("*****************************************\n"); TraversePolynomial(Poly2); AddPolynomial(Poly1,Poly2,Poly3); printf("*****************************************\n"); TraversePolynomial(Poly3); return 0; }
发表评论
-
Java异常的栈轨迹(Stack Trace)
2012-06-06 10:47 2826捕获到异常时,往往需要进行一些处理。比较简单直接的方式 ... -
等值首尾和问题
2011-12-24 00:03 682问题:假设有一个数组x[],有n个元素,并且每一个都大于零;称 ... -
Java并发包中的几种ExecutorService
2011-12-18 13:28 317561.CachedThreadPool Cac ... -
重学数据结构008——AVL树
2011-12-16 19:58 1689之前学习了二叉查找树的及相关操作。二叉查找树的大部分主要 ... -
两数组最小距离问题
2011-12-11 23:26 3216已知两个元素从小到大排列的数组x[]和y[], ... -
等值数目问题
2011-11-27 00:44 671问题描述:已知两个整型数组f[]和g[],它们的元素都已经从小 ... -
重学数据结构007——二叉查找树
2011-11-22 21:36 1682之前的博客中提到过,我学习采用 ... -
重学数据结构006——中缀表达式转后缀表达式
2011-11-18 21:38 3196我们在数学中常见的计算式,例如2+(3*4)叫 ... -
重学数据结构005——栈的应用之平衡符号
2011-11-18 12:01 2315之前学习了栈的基本操作,并且学习了栈 ... -
重学数据结构004——栈的基本操作及实现(数组实现)
2011-11-17 23:13 1384上文提到过栈以及栈的基本操作。上文中是基于链表做的实现 ... -
重学数据结构003——栈的基本操作及实现(链式存储)
2011-11-14 23:19 19101.栈的概念 展示只允许在其一端进行插入语删除操 ... -
重学数据结构002——桶排序、基数排序
2011-11-11 17:17 20041.桶排序 ... -
Java多线程笔记2——线程的状态
2011-11-10 13:28 1008一般来说,线程都具有5种状态:新建、就绪、运行、阻塞、终止。这 ... -
Java泛型学习笔记1
2011-10-28 21:21 987泛型可以解决数据类型的安全问题,其主要方法是在类声 ... -
在MacOS Lion上编译GCC4.6.1
2011-10-28 13:15 0翻译文章,原文地址:h ... -
C语言中指针的操作
2011-10-23 00:27 2404C语言中指针操作主要有以下几种: 指针赋值(assignm ... -
Java多线程笔记1——多线程两种实现方式
2011-10-21 23:35 1903Java中,实现多线程有两种途径:继承java.lan ... -
1.单例模式Singleton
2011-10-18 16:50 940单例模式:Ensure a class has only on ... -
Java 日期处理常见情况
2011-01-03 21:08 1053见代码和注释 1import java.text.Simpl ... -
Java数组初始化
2011-03-25 11:25 1064http://wawlian.javaeye.com/blog ...
相关推荐
利用C语言中的链表实现一元多项式算法,十分实用,便于c爱好者学习链表结构。
在visual c++6.0环境中 链表 动态链表 多项式相加
数据结构 链表 多项式相加 C语言 struct node { int coef; int expo; struct node *next; }; void input(struct node **head) void display(struct node *head) void add(struct node **head1,struct node *head2...
数据结构 C语言 动态链表 议员多项式的加减法 数据结构C语言 一元多项式的加减法算法实现 代码,用vs运行,已测试成功运行,
c语言实现一元多项式相加,用两种方法实现,数组和链表!
严蔚敏 《数据结构》C语言版本第二章链表应用中有多项式加法的应用。本程序能对两个输入的多项式相加,并输出相加的结果。多项式可以一次性输入完成,并用(0,0)表示结束。
一元多项式的加法运算,数据结构链表实现,代码加实验报告
本程序配合清华大学出版社 《数据结构(C语言版)》P39页 在WIT-TC下调试通过
本程序是用C语言实现了一元多项式一元多项式求导、相加和相乘。
一元多项式相加 求两个一元多项式 A(x) = a0 + a1x + a2x2 + … + anxn 和 B(x) = b0 + b1x + b2x2 + … + bmxm 的和。 要求:分别输入两个多项式的各个系数和指数。要求程序输出多项式的和。 实现是用单链表实现。 ...
C语言版针对数据结构,关于链表的使用,编辑一个小程序进行多项式相加的工呢
一元多项式的相乘(C链表实现),包括多项式的创建、相加和相乘的实现。
一元多项式相加 成绩 10 开启时间 2021年04月25日 星期日 00:00 折扣 0.8 折扣时间 2021年05月20日 星期四 23:59 允许迟交 否 关闭时间 2021年05月30日 星期日 23:59 题目说明: 编写一元多项式加法运算程序。要求用...
数据结构实验:使用链表操作实现多项式相加减和乘法操作!
C语言实现单链表方式的一元多项式的加法
该程序已经调试通过可以运行的,用链表实现多项式的相加问题
c语言链表实现两个一元递增多项式的相加,并输出其结果
c语言链表实现两个一元递增多项式的相加.zip
用单链表实现两个多项式的相加。压缩文件里是一个工程。可用VC直接打开工程。
语言:C语言 实验一:一元多项式相加(链表应用实验) 实验二:串模式匹配算法(串实验) 实验三:二叉树遍历与路径查找(二叉树实验) 内含源程序,实验报告