Question

数据结构作业两道

作业1：已知长度为N的线性表A采用顺序存储结构，请写出一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

具体要求：编写一个函数实现题目的要求，数据元素的类型设为int，函数可以设为
void DeleteItem(SqList&L, int item)
注意item可能在顺序表中出现多次，要求一次循环删除所有的item，每个数据元素被移动的次数至多一次。

作业2：设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转，且仍利用原表的存储空间。
具体要求：编写一个函数实现题目的要求，函数可以设为
void InverseList(LinkList L)
链表逆转后，头指针保持不变，头结点的指针指向原链表最后一个结点，该结点的指针指向原链表倒数第二个结点，依次类推，原首元结点的指针为空指针。
注意通用性，即使原链表为空表，程序也要能正确运行。

Answer 1

作业一代码如下：

#include <stdlib.h>

#include <iostream>

using namespace std;

#define LIST_INIT_SIZE 100 //定义顺序表中元素个数最多有几个

#define LISTINCREMENT 10

typedef struct SqList{

int *elem; //elementtype是元素的类型 依具体情况而定

int length; // 当前长度

int listsize; // 当前分配的存储容量

}SqList; 

void DeleteItem(SqList &L, int item);

void AddItem(SqList &L, int item);

void InitList(SqList &L);

SqList list;

void main()

{

int data;

int i = 0;

int *p;

InitList(list);

cout << "input data : " << endl;

for (i=0; i<10; i++)

{

cin >> data;

AddItem(list, data);

}

for (i=0; i<list.length; i++)

{

//p = &list.elem[i];

cout << list.elem[i] << " ";

}

cout << endl;

DeleteItem(list, 2);

for (i=0; i<list.length; i++)

{

//p = &list.elem[i];

cout << list.elem[i] << " ";

}

cout << endl;

}

void InitList(SqList &L)

{

L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));

if (!L.elem)

return;

L.length = 0;

L.listsize = LIST_INIT_SIZE;

return ;

}

void AddItem(SqList &L, int item)

{

/*

int *q;

q = &L.elem[L.length];

*q = item;

*/

L.elem[L.length] = item;

++L.length;

}

void DeleteItem(SqList &L, int item)

{

int i = 0;

int j = 0;

int first = 0; // 第一个被删除元素位置

int second = 0; // 第二个被删除元素位置

int count = 0; // 总共有几个

// 先标记出位置，然后再移动后面的元素

for (i = 0; i < L.length; i++)

{

if (L.elem[i] == item && !first)

{

count++;

first = i;

if (i == L.length) // 只有一个数并且在最末尾的情况。

{

L.elem[L.length] = 0;

L.length--;

return;

}

else

{

continue;

}

}

// 中间数据的移动

if (!second && (first != second) && L.elem[i] == item) // 当最少有2个数字

{

second = i;

// 

for (j = first - count + 1; j < second; j++)

{

L.elem[j] = L.elem[j+count];

}

first = second;

second = 0;

count++;

}

// 当只有最后一个数需要移动

if (first > 0 && second == 0 && i == L.length - 1)

{

// 

for (j = first - count + 1; j < L.length; j++)

{

L.elem[j] = L.elem[j+count];

}

}

}

L.length = L.length - count;

}

// 默认删除数字2，可以修改输入删除其他数字。

作业二，源代码：

//#include "stdafx.h"

#include <stdlib.h>

#include <iostream>

using namespace std;

typedef struct NODE {

int data;

struct NODE *next;

} LinkList;

LinkList *pHeadLa;

void InverseList(LinkList *L);

void InputData(LinkList * pHead);

void OutputData(LinkList * pHead);

void main()

{

pHeadLa = (LinkList *)malloc(sizeof(LinkList));

pHeadLa->data = 0;

pHeadLa->next = NULL;

cout << "Input data, please!" << endl;

InputData(pHeadLa);

OutputData(pHeadLa);

InverseList(pHeadLa);

OutputData(pHeadLa);

}

// 输入链表存储

void InputData(LinkList * pHead)

{

int count = 10;

LinkList *p = pHead;

while(count-- > 0)

{

p->next = (LinkList *)malloc(sizeof(LinkList));

cin >> p->next->data;

p->next->next = NULL;

p = p->next;

}

}

void OutputData(LinkList * pHead)

{

LinkList *p = pHead;

while(p->next)

{

cout << p->next->data << " ";

p = p->next;

}

cout << endl;

}

void InverseList(LinkList *L)

{

LinkList *p = L;

LinkList *p1;

LinkList *p2;

LinkList *p3;

// 空表 或者 只有一个节点

if (L->next == NULL || L->next->next == NULL)

{

return;

}

p1 = p->next;

p2 = p->next->next;

p3 = p->next->next->next;

// 有2个节点

if (p->next->next->next == NULL)

{

p->next = p2;

p2->next = p1;

p1->next = NULL;

}

// 最少有3个节点

while(1)

{

p2->next = p1;

if (p1 == L->next) // P1第一个节点

{

p1->next = NULL;

}

if (p3->next) // 未到达末尾点

{

p = p1;

p1 = p2;

p2 = p3;

p3 = p3->next;

}

else // 到达末尾点

{

p3->next = p2;

L->next = p3;

break;

}

}

}

运行结果：

追问

迟到了，点赞！