工大数据结构第二章作业(7)

typedef celltype *position;//位置的型 typedef celltype *DLIST;//双向链表的型

//插入元素,在p后面插入

void insert(position p,Elementtype x) { if(p->next){ position q = new celltype; q->element = x; q->next = p->next; q->previous = p; p->next->previous = q; p->next = q; } else { position q = new celltype; q->element = x; q->next = p->next; q->previous = p; p->next = q; } }

//删除中间结点

void Delete(position p) { if(p->next != NULL && p->previous != NULL)//删除的不是头尾结点 { p->previous->next = p->next; p->next->previous = p->previous; delete p; } else cout<<\不能删除头尾结点！\}

void create(DLIST &head)//创建双向链表 { head->previous = NULL;//让头结点的前驱指向自己 head->next = NULL; position p = head; int x=0,i=1; while(1){

cout<<\请输入第\个插入的元素（输入-1结束创建）：\ cin>>x; if(x !=-1) { insert(p,x); p = p->next; } else break; } }

void print(DLIST head)//输出链表元素 { position temp = head; while (temp->next) { temp=temp->next; cout<element<<'\\t'; } cout<

int swap(Elementtype x,DLIST &head)//查找交换 { position temp,L; temp = head; while (temp->next) { temp=temp->next; if (temp->element==x&&temp->previous!=head)//元素匹配并且前驱不能是头结点 { L = temp->previous; L->previous->next = temp; temp->previous = L->previous; L->next = temp->next; temp->next->previous = L; L->previous = temp; temp->next = L; return 1; } } return 0; }

void main() { DLIST head = new celltype; create(head); print(head); Elementtype x; cout<<\请输入你想查找的元素：\ cin>>x; if(swap(x,head)) { cout<<\查找交换成功！\ print(head); } else cout<<\查找失败！\}

十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法

十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。

十三，十四 算法分析:

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。

//三元组表示的稀疏矩阵对角线元素相加，以及稀疏矩阵相加 #include using namespace std;

#define NumVertices 6//稀疏矩阵非零元素个数

struct node{ int row;//行 int col;//列 int data;//值 };

typedef node triple;//三元组

void Input(triple a[])//输入三元组

{ cout<<\请输入系数矩阵的行、列数和非零元素个数：\ cin>>a[0].row>>a[0].col>>a[0].data; if(a[0].row != a[0].col) cout<<\请注意您输入的系数矩阵不是n阶矩阵，无法求对角元素的和！\ for(int i=1;i<=a[0].data;i++) { cout<<\请以按行优先的规则依次输入第<>a[i].row>>a[i].col>>a[i].data; } }

void Init(triple a[])//初始化三元祖 { a[0].row = 4; a[0].col = 4; a[0].data = 6; a[1].row = 0; a[1].col = 0; a[1].data = 50; a[2].row = 1; a[2].col = 0; a[2].data = 10; a[3].row = 1; a[3].col = 2; a[3].data = 20; a[4].row = 3; a[4].col = 0; a[4].data = -30; a[5].row = 3; a[5].col = 2; a[5].data = -60; a[6].row = 3; a[6].col = 3; a[6].data = 5; }

int Find(triple a[],int row,int col)//判断三元组A所标示的稀疏矩阵是否存在下标[row][col]的非零元素,存在的话返回该非零元素 { for(int i=1;i<=a[0].data;i++){ if(a[i].row == row && a[i].col == col) return a[i].data; } return 0; }

int Sum(triple a[])//求对角矩阵对角元素的和 {

int i,sum=0;

if (a[0].row!=a[0].col)

cout<<\此稀疏矩阵不是n*n矩阵，无法求对角元素和\ else

for (i=1; i<=a[0].data; i++)

if (a[i].row==a[i].col ||a[i].row+a[i].col == a[0].row-1) sum+=a[i].data; return sum; }

void Print(triple *a)//输出三元组 { for(int j=0;j<=a[0].data;j++) cout<

void PrintMT(triple *a)//输出三元组所表示的稀疏矩阵 { for(int i=0;i

void Combine(triple a[],triple b[],triple c[])//三元组表示的稀疏矩阵相加 { c[0].row = a[0].row; c[0].col = a[0].col; int cdata = a[0].data+b[0].data;//c的临时非零元素个数 int cmark = 1; for(int i = 0;i