（1）采用一个大小为n的辅助数组b，用于标记链表中的元素是否已经出现过，从头开始遍历链表元素，初次遇到元素时，将b[abs(p->data)]内容置为一，每次遇见元素时,检查数组，若数组内容为1，则删除对应元素
(2)
typedef struct plink
{
int data;
struct plink* link;
}
(3)
对链表进行初始化；
int b[n]=[0];//辅助数组
plink* p1=head->link;
while(p->link!=NULL)
{
if(b[abs(p->data)]==1)
{
plink* s=p->link;
p->link=p->link->link;
free(s);
}
else b[abs(p->data)]=1
}
(4)时间复杂度为o(m),空间复杂度为o(n)
评分及理由
（1）得分及理由（满分3分）
得分：3分
理由：学生给出的基本设计思想与标准答案一致，都是使用辅助数组标记已出现的绝对值，然后遍历链表进行删除操作。思路正确且完整，因此得满分。
（2）得分及理由（满分2分）
得分：1分
理由：学生给出了单链表结点的数据类型定义，基本结构正确，但存在以下问题：
1. 结构体名称使用了"plink"而不是更规范的"node"（虽然这不是错误，但不够标准）
2. 缺少typedef定义，无法直接使用plink作为类型名
3. 缺少指针类型的定义
扣1分，因为虽然基本结构正确，但不够完整和规范。
（3）得分及理由（满分8分）
得分：4分
理由：学生的算法实现存在以下逻辑错误：
1. 数组b的大小应该是n+1而不是n，因为|data|≤n，需要索引0到n
2. 数组初始化语法错误，int b[n]=[0]不是合法的C/C++语法
3. 变量名不一致，开始用p1，后面用p
4. 缺少对头结点的处理，直接使用head->link可能有问题
5. 在删除结点后，p指针没有正确移动，可能导致逻辑错误
6. 缺少malloc/free对辅助数组的动态分配和释放
7. 代码格式和注释不完整
虽然基本思路正确，但由于存在多个逻辑错误和语法问题，扣4分。
（4）...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发