数据结构 |
您所在的位置：网站首页 › 数据结构顺序表排序函数怎么写 › 数据结构 |
数据结构
|
题目：请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)，要求使用最少的附加空间。
解析：可以理解为一个线性表内的交换问题。当n为奇数时，将第一个元素与最后一个元素进行交换，第二个元素与倒数第二个元素进行交换，以此类推，最中间的元素不用进行交换（n/2+1）。当n为偶数时，规则与奇数时一样，只是最中间两个元素也要进行交换（n/2 n/2+1）。
核心代码： //核心代码 void Inverse(SqList &L) { int i, temp; for (i = 0; i < L.length / 2; i++) { temp = L.elem[i]; L.element[i] = L.elem[L.length - 1 - i]; L.element[L.length - 1 - i] = temp; } } //c++版定义结构体 typedef struct { int *elem; int length; } SqList; 第二种方法：头插法简单来说就是创建一个指向首元节点的指针p，不断地将p->next插入到头节点后（p指向的位置始终不变），就可以实现逆置单链表。
代码如下： #include #include using namespace std; typedef struct LNode { int data; struct LNode *next; }LNode, *LinkList; LinkList List_HeadInsert(LinkList &L) { LNode *s; int x=1; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; while(xdata = x; s->next = L->next; L->next = s; x++; } return L; } int len(LinkList L) { int i=0; LNode *p; p = L->next; while(p) { i++; p = p->next; } free(p); return i; } LinkList Reverse(LinkList &L) { int l = len(L); LNode *s; s = L; LNode *p = s->next; LNode *q; while(l-1){ //cout data next; //cout data next = q->next; q->next = s->next; s->next = q; l--; } return L; } int main() { LinkList L = List_HeadInsert(L); LNode *t = L->next; while(t){ cout data next; } cout next; while(p){ cout data next; } return 0; }里面加入了求长度的代码，其实没有必要，判断循环结束的条件可以是p->next是否为空，为空则表明逆置已经完成了。 |
【本文地址】
今日新闻 |
推荐新闻 |